A function that calls itself is not magic — it is stack frames piling up and unwinding. Watch them build, watch the answers come back, and watch naive Fibonacci explode into thousands of redundant calls.
Controls
n5
The Call Stack
step 0
Stack frames (newest on top)
Call trace
Insight
Every call pushes a stack frame holding its arguments, locals and return address. Returning pops it. Recursion is just this, repeated.
total calls0
max depth0
result–
Complexity
factorialO(n)
fib naiveO(2^n)
fib memoisedO(n)
Recursion and the Call Stack
Where beginners get stuck — not on the idea, but on what the machine is actually doing.
Quick Context
Recursion is a function calling itself on a smaller version of the same problem. It needs exactly two things: a base case that stops the descent, and a recursive case that moves toward it.
deffactorial(n):
if n <= 1: return1# base casereturn n * factorial(n - 1) # recursive case
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.
Interactive Exploration Guide
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.
Key Takeaway
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.
Cheat sheet
Recursion and the Call Stack
A function that calls itself is not magic — it is stack frames piling up and unwinding. Watch them build, watch the answers come back, and watch naive Fibonacci explode into thousands of redundant calls.