The Call Stack Does the Remembering
The confusing part is that a recursive function does not finish before calling itself again. factorial(5) must pause, wait for factorial(4), and only then multiply.
Each paused call keeps its own frame — its own copy of n and its own place to resume. Step through and watch frames stack up on the way down, then unwind as answers travel back up. Nothing is computed until the base case is reached; everything is computed on the way back.
Stack Overflow Is Real
Select countdown — no base case. Frames pile up and never pop, because nothing stops the recursion. Memory reserved for the stack is finite, so eventually the program crashes with a stack overflow.
Typical limits are a few thousand frames (Python defaults to 1000). Every recursive function you write needs a base case that is genuinely reachable — a base case that the recursion never hits is no base case at all.
Naive Fibonacci: The Cautionary Tale
Choose fibonacci — naive and raise n. The call counter grows explosively, because fib(n) calls fib(n-1) and fib(n-2), which recompute the same values over and over. That is O(2ⁿ): fib(30) needs over 1.3 million calls to return a number you could compute by hand.
Now switch to memoised at the same n. Results are cached the first time, so each value is computed once and the call count collapses to roughly 2n — from exponential to linear, with a dictionary. That is dynamic programming in one change, and it is the subject of the next module.
When to Use It
Recursion shines on self-similar problems: trees, nested structures, divide-and-conquer, backtracking. Traversing a BST recursively is three lines; iteratively it needs an explicit stack.
Prefer a loop when the problem is linear — a recursive sum of an array just burns stack frames for nothing. And note that some languages (though not Python or JavaScript) optimise tail recursion into a loop, avoiding the stack growth entirely.
A function that calls itself
Recursion solves a problem by solving a smaller instance of the same problem. Two parts are required, and omitting either is the classic failure:
A base case that returns without recursing. A recursive case that moves towards the base case.
def factorial(n):
if n <= 1: # base case
return 1
return n * factorial(n - 1) # recursive case, strictly smaller
"Moves towards the base case" is the part that needs checking. factorial(n - 1) reduces n by one, so it must eventually reach 1. A recursive call that does not strictly reduce the problem produces infinite recursion, and Python raises RecursionError after about 1,000 frames.
What the call stack actually holds
Each call allocates a frame containing the function's local variables, its arguments, and where to return to. Frames stack up, and unwind as calls return.
Tracing factorial(4):
| Stack (top last) | Action |
|---|
| factorial(4) | calls factorial(3) |
| factorial(4), factorial(3) | calls factorial(2) |
| factorial(4), factorial(3), factorial(2) | calls factorial(1) |
| … factorial(1) | returns 1 |
| … factorial(2) | returns 2 |
| factorial(4), factorial(3) | returns 6 |
| factorial(4) | returns 24 |
Two consequences follow directly.
Recursion depth costs memory. Depth n means n frames, so recursion is O(n) space even when the equivalent loop is O(1).
The stack has a limit. Python's is around 1,000 frames by default, deliberately conservative to fail cleanly rather than segfaulting. That limit is why recursion over a large list or a long chain must be converted to iteration.
import sys
sys.setrecursionlimit(10_000) # raises the limit, up to the real C stack
Raising it works and moves the failure mode from a clean exception to a possible crash. Converting to iteration is the more robust answer.
Where recursion is the natural expression
Recursion is not a general substitute for loops. It is the right choice when the data or the problem is recursive.
| Problem | Why recursion fits |
|---|
| Tree traversal | A tree's children are trees |
| Divide and conquer | Merge sort, quick sort, binary search |
| Backtracking | Try, recurse, undo |
| Nested structures | JSON, directory trees, expression parsing |
| Graph DFS | The recursion stack is the current path |
| Mathematical recurrences | Fibonacci, Catalan numbers, Ackermann |
Iterating over a flat list, by contrast, is a loop — writing it recursively adds stack frames for nothing.
The graph row is worth expanding: DFS's recursion stack holds exactly the path from the root to the current node, which is why cycle detection and topological sorting fall out so naturally. Reproducing that iteratively requires maintaining the path explicitly.
What the stack is holding, and what it costs
Recursion is often explained as a function calling itself, which is the least interesting part of it. The useful mental model is the stack of paused frames, and you can print it: every frame is real, every frame costs memory, and the depth limit is a number you can go and read.
Guided experiments
- Step through factorial(5). Watch five frames build downward, then multiply back up as each returns. Nothing multiplies until the base case is hit.
- Note where the answer appears. All the real work happens during the unwinding, not the descent.
- Run naive fibonacci at n=5, then n=10. The call count roughly quadruples for five extra steps — exponential growth, visible.
- Switch to memoised at the same n. Same answer, a fraction of the calls, because repeats are served from the cache.
- Select countdown with no base case. Frames accumulate without limit — a stack overflow in slow motion.
Summing up
Recursion is the call stack made visible: each call gets a frame, frames build on the way down and unwind on the way back. Always ensure the base case is reachable, and watch for repeated subproblems — memoising them is the difference between exponential and linear.
Converting recursion to iteration
Two situations, and they need different techniques.
Tail recursion — the recursive call is the last operation, with nothing left to do after it — converts to a simple loop:
def factorial_iter(n):
result = 1
for i in range(2, n + 1):
result *= i
return result
Some languages eliminate tail calls automatically so the stack does not grow. Python deliberately does not, on the grounds that stack traces are more valuable for debugging. So tail recursion in Python still consumes frames, and the loop is genuinely better.
Non-tail recursion — work remains after the recursive call, as in tree traversal — needs an explicit stack:
def inorder_iter(root):
out, stack, node = [], [], root
while stack or node:
while node: # go left as far as possible
stack.append(node)
node = node.left
node = stack.pop()
out.append(node.value) # visit
node = node.right # then go right
return out
That is what recursion was doing implicitly. The explicit version is longer and harder to read, which is exactly why recursion is preferred where depth allows.
Memoisation: recursion made efficient
Naive recursive Fibonacci recomputes the same values enormously many times — O(2ⁿ) calls, because fib(n-1) and fib(n-2) share almost all their work.
Caching results collapses it to O(n):
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
return n if n < 2 else fib(n-1) + fib(n-2)
| n | Naive calls | Memoised calls |
|---|
| 20 | 21,891 | 21 |
| 40 | 331,160,281 | 41 |
One decorator, and an impossible computation becomes instant. The requirement is that arguments are hashable — tuples rather than lists.
This is dynamic programming in its top-down form, and it is the single most valuable thing to know about making recursion practical.
Common mistakes
- No base case, or one that is unreachable — infinite recursion.
- A recursive call that does not shrink the problem, which is the same failure in disguise.
- Forgetting to return the recursive result.
factorial(n-1) without return gives None. - Mutable default arguments as accumulators —
def f(n, acc=[]) shares one list across all calls. - Exceeding the recursion limit on deep input; convert to iteration.
- Recomputing subproblems without memoisation, turning a linear problem exponential.
- Recursing over a flat structure where a loop is clearer and cheaper.
Questions people ask
Is recursion slower than iteration? In Python, yes — each call has function-call overhead and a frame. Prefer it for clarity on recursive structures, not for speed.
Why does Python limit recursion depth? To raise a clean RecursionError rather than overflowing the C stack and crashing.
Does Python optimise tail calls? No, deliberately — the maintainers prioritise usable stack traces.
How deep can I recurse? About 1,000 frames by default; raising the limit works up to the actual stack size.
When should I choose recursion? When the data is recursive — trees, nested structures, divide and conquer, backtracking.
What is mutual recursion? Two functions calling each other, which is common in recursive-descent parsers.
Recap in one screen
- A base case and a strictly smaller recursive case are both required.
- Each call holds a stack frame, so depth n costs O(n) memory and Python caps it around 1,000.
- Recursion fits recursive data: trees, nested structures, divide and conquer, backtracking, DFS.
- Tail recursion converts to a loop; non-tail recursion needs an explicit stack, which is why recursion reads better.
@lru_cache turns exponential recursion into linear — the most valuable single line in this topic.