Move it step by step
- factorial(4)running now
Values returned so far (in return order)
No call has returned yet.
- Call running now
- Call waiting for a return
- Returned value
- Empty slot
The boxes in the figure are calls that haven't returned an answer yet. They're called from the bottom up, and they return from the top down.
Step 1 of 81 calls so far1 on the stack
Calling factorial(4). There is 1 call on the stack.
The pseudocode line currently running
- 1factorial(n)
- 2if n == 1:
- 3return 1 (base case, unwind here)
- 4r = call factorial(n - 1) and wait
- 5return n × r
Change the example
Try predicting
You're on step 1.
Which call happens next?
What you'll learn
- How calls pile up each time a function calls itself
- Why the base case makes it unwind, with values returning in reverse order
Prerequisites
- Function calls and return
- Stacks (the last thing pushed comes out first)
How this recursion works
Recursion solves a problem by having a function call itself on a smaller version of the same problem. For a factorial, n factorial can be written as n × (the factorial of n - 1).
If you keep making the problem smaller, you eventually reach a case where the answer is immediately obvious. That's called the base case. Without one, the calls never stop, the stack of pending calls overflows, and you get an error.
Steps, with an example
- 1If n is 1, return 1 without calling again (this is the base case)
- 2Otherwise, call factorial(n - 1) and wait for the answer
- 3Multiply the returned value by n and return it
- 4A call that has returned drops off the stack, and the call one level down continues
| Call | What it does | Return value |
|---|---|---|
| factorial(4) | 4 × factorial(3) | 24 |
| factorial(3) | 3 × factorial(2) | 6 |
| factorial(2) | 2 × factorial(1) | 2 |
| factorial(1) | Base case. Returns 1 without calling. | 1 |
Call count and complexity
| What's counted | Count | Complexity |
|---|---|---|
| Number of calls | n calls | O(n) |
| Number of multiplications | n - 1 times | O(n) |
| Deepest stack size | n frames (uses that much memory) | O(n) |
If n is 6, it calls 6 times, and at its deepest point 6 calls are on the stack. Python stops with a RecursionError at around 1000 stacked frames by default, so very deep recursion is usually rewritten as a loop.
When to use it
Good fit
- The problem breaks down into a smaller version of itself (factorials, folders inside folders)
- Traversing a tree or graph in depth (depth-first search)
- Splitting work up, solving the pieces, then combining them (merge sort)
Not a good fit
- The recursion would go tens of thousands of levels deep (the stack overflows; use a loop instead)
- The same call would be repeated many times (you need to cache results)
Code
Pseudocode
- 1factorial(n)
- 2if n == 1:
- 3return 1 (base case, unwind here)
- 4r = call factorial(n - 1) and wait
- 5return n × r
Working code
▶ Press “Run” to see the result here
Edit the Python or JavaScript and press “Run” to see the result right away. Java is read-only here.
FAQ
- What happens if you forget to write a base case?
- Calls like factorial(0) or factorial(-1) never stop piling up, and eventually they overflow. Python raises RecursionError, and Java throws StackOverflowError.
- How does this relate to a stack?
- Calls that haven't returned yet pile up just like a stack, and the last one called is the first to return. This pile of pending calls is called the call stack.
- Is this better than writing it with a loop?
- For a factorial, a loop is faster and has no depth to worry about. Recursion is worth using for problems that read more clearly when you split them up, like traversing a tree.
