How does this recursive function in Python work?

Question

I am learning python from the Book: "ThinkPython".

At page 56 (Chapter 6. Fruitful functions) there is a recursive function that calculates the factorial of any number. It does work, however I don't understand why. This is the code:

def factorial(n):
    if n == 0:
        return 1
    else:
        recurse = factorial(n-1)
        result = n * recurse
        return result

Let's say I try with 3, I guess this is what should happen:

enters the factorial function and n=3
enters the else statement because n is not 0
and here goes back to the beginning to step 1 with n = 2

so it should do the same until n = 0 and return 1 (it will never get to the last lines).

"goes back to the beginning" may be the source of your misunderstanding. Multiple instances of a function can exist in the call stack at once, and each one remembers its place. When the second factorial call completes, it returns to the first factorial call, which is still in the `else` block. It's not like a `while` or `for` loop, which returns to the top line. — Kevin, Oct 13 '15 at 14:01
the function follows the definition of factorial(n): `the number n multiplied by the factorial(n-1)`. The test is there to stop it at zero (the base of the recursion). Plenty to read about [recursion](https://en.wikipedia.org/wiki/Recursion_%28computer_science%29) in general — Pynchia, Oct 13 '15 at 14:01
Hint: deduce what happens with that `1`? Is it used in any operation? — Łukasz Rogalski, Oct 13 '15 at 14:01
Possible duplicate of [Understanding how recursive functions work](http://stackoverflow.com/questions/25676961/understanding-how-recursive-functions-work) — tzaman, Oct 13 '15 at 14:08
Yes, I believe what is unclear to the OP is the fact that `recurse = factorial(n-1)` doesn't just `go back to the beginning` of the function, but it **calls** the function once more — Pynchia, Oct 13 '15 at 14:08
IME, people don't understand recursion merely by reading explanations. You've got to pretend you're the interpreter and go through the steps yourself to see what's happening. FWIW, when I was learning this stuff I found making diagrams on big sheets of paper very helpful. — PM 2Ring, Oct 13 '15 at 14:37
If one of the answers below fixes your issue, you should accept it (click the check mark next to the appropriate answer). That does two things. It lets everyone know your issue has been resolved to your satisfaction, and it gives the person that helps you credit for the assist. [See here](http://meta.stackexchange.com/a/5235) for a full explanation. — Morgan Thrapp, Oct 23 '15 at 14:10

score 4 · Answer 1 · edited Oct 23 '15 at 16:32

Your function is:

def factorial(n):
 if n == 0:
  return 1
 else:
  recurse = factorial(n-1)
  result = n * recurse
  return result

Let's go through an execution of this function step-by-step, starting with n = 3.

Entering 
STATE 1 
n = 3 
recurse = factorial(3-1)

STATE 2
n = 2
recurse = factorial(2-1)

STATE 3
n = 1
recurse = factorial(1-1)

STATE 4
You now have an n = 0, so you return 1 to STATE 3.

STATE 3
n = 1
recurse = 1
result = 1
return result to STATE 2

STATE 2
n = 2
recurse = 1
result = 2 * 1 = 2
return result to STATE 1

STATE 1
n = 3
recurse = 2
result = 3 * 2 = 6

And then 6, the factorial of 3, is returned to the calling function :D

Recursion really is a tricky thing to confront, it just takes time to get used to it and to the different ways that it can be used.

Well said, Valerie. I'm a big fan of manually going through the steps like this in order to understand how algorithms work. — PM 2Ring, Oct 13 '15 at 14:37

score 1 · Answer 2 · answered Oct 13 '15 at 14:04

You're correct, as far as you go. However, you don't continue far enough. When the factorial(0) call returns, where does it return to? it returns to the

recurse = factorial (n - 1)

line where n = 1, and then you continue on from there. So, recurse = 1, result = 1* 1 = 1, and returns 1. Again, that goes to the recurse = line in the n=2 case.so, result = 2*1 = 2, and returns that, to the recurse = line where n = 3, so result = 2 * 3 = 6, which is what gets returned.

score 1 · Answer 3 · edited Oct 13 '15 at 14:10

The factorial of n is defined as n * (n-1) * (n-2) etc until 1

So for n = 5 -> 5*4*3*2*1

In the code the factorial is defined as n * whatever the factorial of n-1 is

Python will find out this last part by asking itself: what is the factorial of n-1? Well it is (n-1) * whatever the factorial of (n-1)-1 is.

Do you see the loop/ recursion?

Since for n==0 the factorial will return 1, python can ask itself over and over again what the recursive part is, until it asks itself, what is the factorial of 0?. This part is hardcoded in the first part.

Once it enters this last part, it knows the other answers too! For n == 5:

The factorial is 5 * (factorial of 4)
- The factorial is 4 * (factorial of 3)
  - ...
    - The factorial of 0 is 1.

The factorial of 5 = 5*4*3*2*1

How does this recursive function in Python work?

3 Answers3