Recursion Masterclass: Double Recursion and the Fibonacci Call Tree
Master double recursion with Fibonacci — the base case, the two-call recursive step, a full call-stack walkthrough, complexity, and why it is exponential.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Most recursion tutorials show you a function that calls itself once — factorial, sum of a list, walking a linked list. Those are the training wheels. The moment a single call spawns two recursive calls, the shape of the computation changes completely: you get a branching tree instead of a straight line, and the cost explodes.
Fibonacci is the cleanest example of that jump. fib(n) = fib(n-1) + fib(n-2) is four symbols of math, but implemented naively it recomputes the same subproblems millions of times. Understand exactly why, and you understand the difference between recursion that is elegant and recursion that is a trap.
The problem
The Fibonacci sequence starts 0, 1, 1, 2, 3, 5, 8, 13, ... — every number is the sum of the two before it. Given a non-negative integer n, return the nth Fibonacci number.
The definition is recursive by nature:
fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2) for n >= 2
Input: n = 5
Output: 5 // 0, 1, 1, 2, 3, 5 → the 5th termTwo things make this the canonical recursion lesson:
- There are two base cases (
n = 0andn = 1), and getting them right is half the battle. - The recursive case makes two calls, so the work branches. This is double recursion, and it is where naive recursion goes from linear to exponential.
The brute force baseline
The direct translation of the math is almost suspiciously short:
function fib(n) {
if (n <= 1) return n; // covers fib(0)=0 and fib(1)=1
return fib(n - 1) + fib(n - 2); // two recursive calls
}It is correct. It is also slow in a way that sneaks up on you. Each call fans out into two more, and nothing is remembered between branches. Computing fib(5) computes fib(3) twice, fib(2) three times, fib(1) five times. The redundant work doubles roughly every time n grows by one.
Concretely, fib(30) triggers over 2.6 million calls. fib(50) would take minutes. The tree of calls is fat with duplicates, and that duplication — overlapping subproblems — is the entire performance story.
The key insight: one call, two children
The reframe is to stop thinking of fib as a formula and start thinking of it as a call tree.
Every non-base call fib(n) has exactly two children: fib(n-1) on the left and fib(n-2) on the right. A base case (n <= 1) is a leaf — it returns immediately without branching. The value at any node is the sum of its two children's values, computed only after both have returned.
That gives recursion its execution rhythm, driven by the call stack:
- Descend left as far as possible, pushing a frame for each call, until you hit a base case.
- Return the base value and pop that frame.
- Combine: once both children of a node have returned, add them, store the result, and pop the parent.
The stack only ever holds the frames along the current root-to-node path — never the whole tree. That is why the time is exponential (the tree has exponentially many nodes) but the space is merely linear (the path is at most n deep). Keeping those two facts separate is the masterclass.
The optimal solution
This is the exact implementation the visualizer traces, node by node:
// Fibonacci — classic double recursion
var fib = function (n) {
if (n <= 1) return n; // base cases: fib(0)=0, fib(1)=1
return fib(n - 1) + fib(n - 2);
};"Optimal" here means optimal expression of the double-recursion pattern, not optimal performance — this is the version whose call tree you must be able to draw from memory. The single if (n <= 1) return n line is doing double duty, collapsing both base cases into one check because fib(0) returns 0 and fib(1) returns 1 — the input equals the answer at both leaves.
The evaluation order is fixed by JavaScript: fib(n - 1) is fully resolved before fib(n - 2) even starts. That is why the trace always dives down the entire left spine first, then unwinds and works the right branches.
Walkthrough: fib(4) = 3
Tracing fib(4) shows the descend-return-combine rhythm and the overlapping fib(2) that gets computed twice. The call tree has 9 nodes; here is the order the code actually visits them, with the live call stack after each action.
| Step | Action | Returns | Call stack (bottom → top) |
|---|---|---|---|
| 1 | call fib(4), descend left | — | fib(4) |
| 2 | call fib(3), descend left | — | fib(4), fib(3) |
| 3 | call fib(2), descend left | — | fib(4), fib(3), fib(2) |
| 4 | call fib(1) → base case | 1 | fib(4), fib(3), fib(2) |
| 5 | right child: call fib(0) → base | 0 | fib(4), fib(3), fib(2) |
| 6 | combine fib(2) = 1 + 0 | 1 | fib(4), fib(3) |
| 7 | right child: call fib(1) → base | 1 | fib(4), fib(3) |
| 8 | combine fib(3) = 1 + 1 | 2 | fib(4) |
| 9 | right child: call fib(2), descend | — | fib(4), fib(2) |
| 10 | call fib(1) → base | 1 | fib(4), fib(2) |
| 11 | right child: call fib(0) → base | 0 | fib(4), fib(2) |
| 12 | combine fib(2) = 1 + 0 | 1 | fib(4) |
| 13 | combine fib(4) = 2 + 1 | 3 | (empty) |
Notice steps 3–6 and steps 9–12: fib(2) is computed from scratch twice. On fib(4) that is one wasted recomputation; on fib(40) the same duplication compounds into billions. The stack, meanwhile, never held more than three frames — its depth tracks n, not the number of calls.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Naive double recursion | O(φⁿ) ≈ O(1.618ⁿ) | O(n) | Call tree has ~φⁿ nodes; stack depth is the longest path, at most n |
| Memoized recursion | O(n) | O(n) | Each fib(k) computed once, cached; still n stack frames |
| Bottom-up iteration | O(n) | O(1) | Loop keeping only the last two values |
People often say the naive version is O(2ⁿ). It is actually O(φⁿ) where φ ≈ 1.618 (the golden ratio), because the right subtree fib(n-2) is one level shorter than the left — the tree is not perfectly full. Either way it is exponential, and either way the fix is to stop recomputing: caching results (memoization) or building up from the base collapses time to O(n).
Common mistakes
- Forgetting a base case.
if (n === 0) return 0alone letsfib(1)fall through intofib(0) + fib(-1), andfib(-1)recurses forever until the stack overflows. Then <= 1guard covers both leaves at once. - Returning the wrong base value. Writing
return 1for both base cases gives the offset sequence1, 1, 2, 3, 5..., so every answer is shifted. At the leaves the return value must equaln. - Assuming it is O(2ⁿ) and stopping there. The point is not the exact exponent — it is that the same subproblems are recomputed. That observation is the doorway to memoization and dynamic programming.
- Trusting recursion for large n. JavaScript does not optimize tail calls, and this isn't even tail-recursive. Past a few thousand frames deep you hit a stack overflow — deep recursion belongs as an iterative loop.
Where this pattern shows up next
Double recursion is the loud, exponential cousin. The quieter single recursion patterns are worth mastering first, because they show the same descend-and-combine rhythm without the branching cost:
- Sum of First N Numbers — one recursive call,
n + sum(n-1), the simplest linear recursion. - Sum of All Numbers in Array — recursing over an array by shrinking the index.
- Factorial of N —
n * factorial(n-1), the multiplicative sibling of the sum. - Power of Two — recursion that halves the input each step for O(log n) depth.
You can also step through the Fibonacci call tree interactively and watch the stack push, the base cases fire, and the values combine on the way back up.
FAQ
Why is naive Fibonacci recursion so slow?
Because it recomputes the same subproblems over and over. Calling fib(n) spawns fib(n-1) and fib(n-2), and those overlap heavily — fib(2) alone gets recalculated many times for even modest n. Nothing is cached between branches, so the number of calls grows exponentially (about φⁿ ≈ 1.618ⁿ). Adding memoization to store each computed value drops it to O(n).
What is double recursion?
Double recursion is when a single function call makes two recursive calls to itself, as in fib(n-1) + fib(n-2). This causes the computation to branch into a tree rather than a straight line, so the number of total calls can grow exponentially with the input. It contrasts with single recursion (like factorial), where each call spawns exactly one further call and the work stays linear.
How many base cases does Fibonacci need?
It needs two: fib(0) = 0 and fib(1) = 1. The recursive step fib(n-1) + fib(n-2) reaches back two positions, so a single base case would let one of the two calls slip past it into negative arguments and recurse forever. The compact guard if (n <= 1) return n handles both, since the return value equals n at each leaf.
What is the space complexity of recursive Fibonacci?
O(n), even though the time is exponential. The call stack only holds the frames along the current path from the root down to the node being evaluated, and that path is at most n deep. The tree has exponentially many nodes, but they are never all on the stack at once — each frame is popped as soon as its two children return.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.