Menu
I'm really trying to wrap my brain around how recursion works and understand recursive algorithms. For example, the code below returns 120 when I enter 5, excuse my ignorance, and I'm just not seeing why?
def fact(n):
if n == 0:
return 1
else:
return n * fact(n-1)
answer = int (raw_input('Enter some number: '))
print fact(answer)
415
Python also accepts function recursion, which means a defined function can call itself. Recursion is a common mathematical and programming concept. It means that a function calls itself. This has the benefit of meaning that you can loop through data to reach a result.
A recursive function always has to say when to stop repeating itself. There should always be two parts to a recursive function: the recursive case and the base case. The recursive case is when the function calls itself. The base case is when the function stops calling itself.
In the above example, factorial() is a recursive function as it calls itself. When we call this function with a positive integer, it will recursively call itself by decreasing the number. Each function multiplies the number with the factorial of the number below it until it is equal to one.
lets walk through the execution.
fact(5):
5 is not 0, so fact(5) = 5 * fact(4)
what is fact(4)?
fact(4):
4 is not 0, so fact(4) = 4 * fact(3)
what is fact(3)?
fact(3):
3 is not 0, so fact(3) = 3 * fact(2)
what is fact(2)?
fact(2):
2 is not 0, so fact(2) = 2 * fact(1)
what is fact(1)?
fact(1):
1 is not 0, so fact(1) = 1 * fact(0)
what is fact(0)?
fact(0):
0 IS 0, so fact(0) is 1
Now lets gather our result.
fact(5) = 5* fact(4)
substitute in our result for fact(4)
fact(5) = 5 * 4 * fact(3)
substitute in our result for fact(3)
fact(5) = 5 * 4 * 3 * fact(2)
substitute in our result for fact(2)
fact(5) = 5 * 4 * 3 * 2 * fact(1)
substitute in our result for fact(1)
fact(5) = 5 * 4 * 3 * 2 * 1 * fact(0)
substitute in our result for fact(0)
fact(5) = 5 * 4 * 3 * 2 * 1 * 1 = 120
And there you have it. Recursion is the process of breaking a larger problem down by looking at it as successfully smaller problems until you reach a trivial (or "base") case.
110
Break the problem down into its execution steps.
fact(5)
| 5 * fact(4)
|| 5 * (4 * fact(3))
||| 5 * (4 * (3 * fact(2))
|||| 5 * (4 * (3 * (2 * fact(1))))
||||| 5 * (4 * (3 * (2 * (1 * fact(0)))))
|||||| 5 * 4 * 3 * 2 * 1 * 1
120
Your function simply calls itself, just as any other function can call it. In this case however, your function needs a stopping point so that it doesn't infinitely recurse (causing a Stack Overflow!). In your case this is when n is 0 (it should probably be 1 instead).
25
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
