The Call Stack
How Python keeps track.
When a function calls another function, Python has to remember where it was, so it can come back later. It keeps those notes on a stack, called the call stack. Recursion simply puts many calls on that stack at once.

- Python must remember where it was
- Notes on a stack
- Recursion stacks many calls
Watching the stack
We add a depth argument, and indent each line to show how deep we are. Every call goes one level deeper, and waits. When the base case returns, the waiting calls finish in reverse order, last in, first out. Run it. You can see the calls stack up, and then unwind.
def factorial(n, depth=0):
pad = " " * depth
print(f"{pad}factorial({n}) called")
if n <= 1:
result = 1
else:
result = n * factorial(n - 1, depth + 1)
print(f"{pad}factorial({n}) returns {result}")
return result
factorial(4)factorial(4) called
factorial(3) called
factorial(2) called
factorial(1) called
factorial(1) returns 1
factorial(2) returns 2
factorial(3) returns 6
factorial(4) returns 24The cost of recursion
Every waiting call uses a little memory on the call stack. So recursion that goes N levels deep uses O of N space, even if it looks like it uses nothing. And Python limits how deep the stack can go, to about a thousand calls by default.
| key | value |
|---|---|
| Each call | a frame on the stack |
| Unwinding | last in, first out |
| Depth n | O(n) space |
| Default limit | about 1000 calls |
Summary
The call stack holds every waiting call, and unwinds last in, first out. Deep recursion uses memory. Next, what happens when recursion goes wrong.
Key takeaways- Calls wait on a stack
- Unwind in reverse
- Depth costs memory