Course 3.2Lesson 2 of 5
The factorial is the famous example: n factorial is n times the factorial of n minus 1, and the factorial of 1 is 1, which is the base case. The calls go down to the base case, and the answers come back up, each call multiplying the answer it receives. While the base case runs, all the calls above it are waiting, each holding its own n, and Python keeps them in a pile called the call stack. A function that prints its calls with indents shows the calls going down and the answers coming back.
Try the code and the simulations beside the lesson.
After this lesson you can
You know . Notice that , because . And . A factorial is a number times a smaller factorial. This is a recursive idea already, before any code. The smallest one is : the base case.
Predict first. factorial(4) calls factorial(3), which calls factorial(2), and so on. In what order are the answers worked out? Then run it.
The first part is short and clear.
if n == 1: return 1. The answer is known, and the calls stop.return n * factorial(n - 1). We trust that factorial(n - 1) gives the right answer for the smaller problem, and multiply it by n.The second part of the program shows what happens inside. Each call prints a line when it is called, indented more and more as the calls go down. Then each prints a line when it gives back its answer, as the calls come back up:
factorial(1) gives back 1.factorial(2) gives back 2 * 1 = 2.factorial(3) gives back 3 * 2 = 6.factorial(4) gives back 4 * 6 = 24.Notice the order: the first call is the last to give its answer. It has to wait for all the others.
While factorial(1) runs, the three calls above it are waiting, each one holding its own n and a half-finished multiplication. Python keeps them in a pile called the call stack, like plates in a pile: the last plate put on is the first one taken off. When the base case answers, the pile is unwound, one call at a time, from the top.
A trace table shows the pile at each moment.
| Moment | Calls waiting (top first) | What happens |
|---|---|---|
| 1 | factorial(4) | calls factorial(3) |
| 2 | factorial(3), factorial(4) | calls factorial(2) |
| 3 | factorial(2), factorial(3), factorial(4) | calls factorial(1) |
| 4 | factorial(1), ... | base case: gives back 1 |
| 5 | factorial(2), factorial(3), factorial(4) | 2 * 1, gives back 2 |
| 6 | factorial(3), factorial(4) | 3 * 2, gives back 6 |
| 7 | factorial(4) | 4 * 6, gives back 24 |
The pile has a size limit. That is why a missing base case ends with a RecursionError: the pile of waiting calls got too tall.
The pile is the call stack. It is as tall as the deepest call, which is why a very deep recursion runs out of room.
Beginners often try to follow every call in their heads, and get lost. Do something easier. Write the function in three steps.
factorial(1) is 1.factorial(n - 1) already gives the right answer.n from the answer for n - 1? Multiply by n.Then check one call by hand, for a small n. If it works for the base case, and the step is right, it works for all n. This is the same idea as a row of dominoes: the first one falls, and each one knocks the next.
if n == 0: return 0 for factorial gives 0 for every number, because everything is multiplied by 0. For the factorial, 0! is 1.factorial(0) with the base case n == 1 goes to -1, -2, ..., and never stops.return before n * factorial(n - 1).** The answer is lost, and the function gives None.factorial(-3) never reaches 1.Start with two quick questions. Each New numbers gives you a fresh one, so you can practise as long as you like.
Then the labs and the problems:
sum_to(3).factorial(n) = n * factorial(n - 1), and factorial(1) = 1.Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
factorial(3)?RecursionError?Every lesson is open to read. Enrolling also lets you:
Log in to join the discussion.
Loading…
This lesson is free to read. Enroll free to keep your place and take the tests.