Need help understanding a recursion example in Python

Question

Python is my first programming language, and I'm learning it from "How to Think Like a Computer Scientist". In Chapter 5 the author gives the following example on recursion:

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

I understand that if n = 3, then the function will execute the second branch. But what I don't understand is what happens when the function enters the second branch. Can someone explain it to me?

• ctrl-alt-delor: I thing it is clearer if you rewrite the else part by removing the two temporary variable to be just return factorial(n-1) * n.
• Jan Doggen: Just put 3 in and follow the code all the way through the end. Then 4. Then you'll understand. You could do this on paper.

Answer 1

What happens is that the function is called again, under the control of the first call, and after that there are two invocations of factorial active simultaneously (but the first one is waiting for the second one to return). Each of them has its own copy of n: the subordinate invocation has n == 2 while the original invocation still has n == 3. The subordinate invocation then calls itself another time, and so on, until there are four versions of the function in memory (but the first three are inactive, waiting for the last one to return).

The variable values and return addresses of all those invocations are kept on the call stack, and they disappear automatically when an invocation returns. (This is why a recursion that is too deeply nested can cause the phenomenon that this site was named after: the stack overflow.)

A good way to get your head around what really happens when a recursive function is called is to simulate the call stack with pen and paper, by writing down what versions of n there are at any given time and what their values are. A call to factorial 3 is just the right size for that exercise.

• Ali Mustafa: So the first time the program reaches "recurse", instead of continuing to "result", it goes back to the start and executes factorial (n-1), which also goes back to the start instead of "result" and so on?
• Kilian Foth: Yes, it goes back to the start, but not quite: control flow moves to the start of another copy of the same method. It's not like running around in a circle, more like entering a car park and reaching the entrance of the next higher level.

Answer 2

I have refracted the code, in the hope that it makes it clearer.

def factorial(n): 
 if n < 0: 
 raise ValueError
 if n == 0: 
 return 1 
 else: 
 return factorial(n-1) * n

It says:

• I only work for positive numbers
• 0! = 1
• n! = (n-1)! ×ばつ n

This is the definition: we just write the mathematical definition of factorial in python.

---

Also look at Kilian Foth's answer as it considers stack-overflow problems.

• ctrl-alt-delor: Note: in python, you will get a stack-overflow for large values of n. This is because python has no tail-call optimisation. (This is a design feature, to allow the implementation of full stack tracing.)