# Understanding recursion in Python

Posted on

### Question :

Understanding recursion in Python

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: '))

``````

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.

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).

Keep in mind that each invocation of fact(), whether invoked externally or invoked by itself, gets its own distinct set of local variables.

``````fact(1) has n of 5
fact(2) has n of 4
fact(3) has n of 3
fact(4) has n of 2
fact(5) has n on 1
fact(6) has n of 0
``````

The deepest ones (here, `fact(6)` is deepest) are computed completely before the levels above them in the callstack are able to finish.

So

• `fact(6)` returns a 1 to `fact(5)` (termination case).
• `fact(5)` returns a 1 to `fact(4)` (1*1)
• `fact(4)` returns a 2 to `fact(3)` (2*1)
• `fact(3)` returns a 6 to `fact(2)` (3*2)
• `fact(2)` returns a 24 to `fact(1)` (4*6)
• and finally `fact(1)` returns 120 (5*24) to its caller, whatever that may be.