Recursion and the call stack
easyEvery call gets a stack frame holding its own state. See the frames pile up and unwind, count how many times fib(2) is recomputed, then switch the cache on and watch the tree collapse into a line.
O(n) memoisedWorst O(2ⁿ) naiveSpace O(n) stack depthSaved in this browser - no sign-up, nothing sent anywhere.
How recursion and the call stack works
Every function call gets a stack frame - a small block holding its own arguments, locals and half-finished work. Recursion is just calls stacked on calls: fib(5) cannot return until fib(4) does, so its frame waits underneath. The visualizer draws the frames piling up and unwinding, and that maximum pile height is the space complexity, O(n).
Naive fib is the canonical time disaster. Each call spawns two more, so the tree roughly doubles per level - and it forgets everything. Run fib(5) and fib(2) is rebuilt from scratch three separate times; nothing in the recursion knows it has answered that question before. That blind recomputation, compounded level after level, is what O(2ⁿ) looks like drawn as a picture.
Memoisation fixes exactly that. Cache each result the first time, and every repeated subtree becomes a single lookup: fib(5) drops from 15 calls to 9, and the exponential tree collapses toward a chain. One dictionary turns O(2ⁿ) into O(n), and that single idea, applied systematically, is dynamic programming.
Step by step
- fib(5) pushes the first frame. It needs fib(4) and fib(3) before it can add, so it parks on the stack and waits.
- Calls chase the left branch down: fib(4), fib(3), fib(2), fib(1). Five frames deep - the stack's high-water mark.
- fib(1) hits the base case n <= 1 and returns 1 with no further calls. The stack starts unwinding.
- fib(2) resumes: its right child fib(0) returns 0, so fib(2) = 1 + 0 = 1 and its frame pops.
- Values flow upward as siblings finish: fib(3) = 1 + 1 = 2, then fib(4) = 2 + 1 = 3.
- The right subtrees repeat the story - fib(3) is computed again in full under the root, and fib(2) three times overall.
- fib(5) = 3 + 2 = 5 after 15 calls. Toggle memoisation on: the same answer takes 9, three of them instant cache hits.
Complexity
| Best case time | O(n) memoised |
|---|---|
| Worst case time | O(2ⁿ) naive |
| Space | O(n) stack depth |
Reference implementation
Python
def fib(n):
if n <= 1: # base case - stops the recursion
return n
return fib(n - 1) + fib(n - 2)
# Same function, memoised: O(2^n) becomes O(n).
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
return n if n <= 1 else fib_memo(n - 1) + fib_memo(n - 2)JavaScript
function fib(n) {
if (n <= 1) return n; // base case
return fib(n - 1) + fib(n - 2);
}
// Memoised: each n is computed once.
const memo = new Map();
function fibMemo(n) {
if (n <= 1) return n;
if (memo.has(n)) return memo.get(n);
const r = fibMemo(n - 1) + fibMemo(n - 2);
memo.set(n, r);
return r;
}Worth noticing
The stack is the algorithm's memory
Each call gets a frame holding its own n and its half-finished result. Watch the stack grow to depth n and unwind - that depth is the space complexity, and it is why deep recursion overflows.
fib recomputes the same values over and over
Run fib(6) without memoisation and count how many times fib(2) appears in the tree. Every repeated subtree is wasted work, and the count of them is what makes naive fib O(2ⁿ).
Memoisation turns the tree into a line
Switch the cache on. Each n is computed once and reused; the tree collapses to n nodes and the recursion count drops from exponential to linear. That single change is the whole idea behind dynamic programming.
Linear recursion is just a loop with extra steps
Pick factorial: the stack is a straight chain, each frame waiting on exactly one child. Any recursion shaped like that can be rewritten as a loop, which is what tail-call optimisation does automatically in some languages.
Common pitfalls
- A missing or unreachable base case. Every chain of recursive calls must hit n <= 1; one wrong boundary and the stack grows until the program dies.
- Forgetting that depth is memory. Each live frame occupies stack space, and Python caps the stack near 1,000 frames by default - deep linear recursion overflows even when the maths is fine.
- Recomputing shared subproblems. Naive fib(30) makes about 2.7 million calls for an answer memoisation delivers in around 31 - always ask which subtrees repeat before shipping branching recursion.
- Counting on tail-call optimisation. The factorial-shaped recursion here could run as a loop, but Python never optimises tail calls and V8 does not either - convert it yourself when depth threatens the stack.
Where it is used
- Top-down dynamic programming is literally this: memoised recursion over coin change, edit distance, grid paths.
- Tree and graph traversals - DFS is recursion, and the explicit-stack version exists for when depth exceeds the real stack.
- Reading stack traces: a crash 1,000 frames deep in the same function is this picture, printed by the runtime.
- The interview escalation: write recursive fib, get asked why it is slow, fix it with a cache - this module is that arc.
Frequently asked questions
What is the time and space complexity of recursive Fibonacci?
Naive, the worst case is O(2ⁿ) time - the call tree roughly doubles each level, so fib(5) already makes 15 calls and fib(30) about 2.7 million. Memoised, the best case is O(n), because each value is computed once. Space is O(n) stack depth either way: the deepest live chain runs from fib(n) down to fib(1).
Why does deep recursion cause a stack overflow?
Every unfinished call keeps a live frame holding its state, so depth n means n frames in memory at once. Language runtimes cap that region - Python refuses around 1,000 frames by default - and when recursion depth exceeds the cap, the program dies regardless of how fast the function is.
Is memoisation the same as dynamic programming?
Memoised recursion is dynamic programming in its top-down form. Bottom-up DP fills the same table iteratively from the base cases, trading the call stack for a loop. Both do O(n) work on Fibonacci; the choice usually comes down to stack depth and how naturally the dependency order falls out.
When should I rewrite recursion as a loop?
When the shape is linear - each frame waiting on exactly one child, like the factorial and sumTo options here - the rewrite is mechanical and removes overflow risk entirely. Branching recursion needs an explicit stack to convert. Rewrite whenever depth can reach thousands of frames in a language without tail-call optimisation.