Recursion
- Self-reference: A function refers to itself with its own name.
- Mutual Recursion: Mutual recursive functions call one another
1
2
3
4
5
6
7
8
9
def add_next(n):
print(n)
return lambda f: subtract_next(n+f)
def subtract_next(n):
print(n)
return lambda f: add_next(n-f)
add_next(2500)(500)(1000)(24)
1
2
3
4
5
6
7
8
9
10
2500
3000
2000
2024
<function __main__.subtract_next.<locals>.<lambda>(f)>
- Environmental Diagram:
![Environmental Diagram]()
- Be careful! the return value of the lambdas wasn’t the add_next or subtract_next function. It is the lambda that the functions return.
1
2
3
4
5
def f(x):
print(x)
return f(x+1)
# f(0) This will result in a maximum recursion depth error. There is no base case for the recursion to exit!
- This is an example with a base case
1
2
3
4
5
6
7
8
9
10
11
def fact(n):
"""compute factorial(n) n!
>>> fact(5) # 5! = 5 * 4 * 3 * 2 * 1
120
"""
if n == 0:
return 1
return n * fact(n-1)
fact(500)
1
1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
- This is an example of abstraction and induction. We assume that the function can be stacked on repeated more complex values, but we also use abstraction to assign the complex operations behind a name and just repeat it.
1
2
3
4
5
6
7
8
def fact_iter(n):
result = 1
while (n>0):
result = result * n
n-=1
return result
fact(1000) == fact_iter(1000)
1
True
Example: Boxes and Pyramids
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def boxes_iter(k):
"""prints out k boxes.
>>> boxes_iter(4)
[][][][]
"""
while k > 0:
print(f"[{k}]", end="")
k-=1
return
def boxes_r(k):
if not k:
return
else:
boxes_r(k-1)
print(f"[{k}]", end="")
return
boxes_iter(4)
print()
boxes_r(4)
1
2
[4][3][2][1]
[1][2][3][4]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def pyramid_iter(k):
"""prints out a pyramid of k height.
>>> pyramid(4)
[]
[][]
[][][]
[][][][]
"""
i = 1
while k > i:
print(" ")
boxes_r(k)
k-=1
return
def pyramid(k):
if k == 0:
return
else:
boxes_r(k)
print("")
pyramid(k-1)
pyramid(8)
1
2
3
4
5
6
7
8
[1][2][3][4][5][6][7][8]
[1][2][3][4][5][6][7]
[1][2][3][4][5][6]
[1][2][3][4][5]
[1][2][3][4]
[1][2][3]
[1][2]
[1]
Recursion and Iteration
- Iteration is a special type of recursion