Understanding recursion in Python

Question

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)

You will need to explain to us what exactly you don't understand. What do you think it should return? — svick, Jul 27 '12 at 18:44
You see that inside `fact` that this same `fact` is called again? And that this selfcalling stops when n equals 0 ? And that by every selfcalling n gets one lower? — Marco de Wit, Jul 27 '12 at 18:48
Thanks to all the great explanations. I will definitely practice everyday, as it seems indispensable to writing efficient algorithms. — suffa, Jul 27 '12 at 20:06

score 27 · Accepted Answer · answered Jul 27 '12 at 18:52

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.

Rob Wagner · Answer 2 · 2012-07-27T19:00:11.000

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

score 6 · Answer 3 · edited Nov 19 '19 at 01:11

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.

score 3 · Answer 4 · answered Jul 27 '12 at 18:48

A recursive function is one that calls itself and continues to do so until evaluation is finished and a result is produced. The key with the factorial function you have above is the return x * fact(x-1)

So if you input 5 it will execute 5 * fact(5-1) * fact 4-1) .... And so on until it hits 0 and then returns 1. So you will have 5*4*3*2*1 which is 120.

It continues to allocate variables on the stack. So if you put a number that is too high it could result in a stack overflow exception. Unless you use something called tail call optimization (TCO) which turns the recursive function into a for loop and cleans up the memory allocated.

Understanding recursion in Python

4 Answers4

Linked

Related