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?
2
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.
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.
1