Fibonacci —
Two branches, and one of them repeats.
Naive recursive Fibonacci calls itself twice per call — once for n-1, once for n-2 — and those two branches end up recomputing the exact same smaller values over and over. Watch the call tree branch on LearnBug and see fib(3) get computed twice inside fib(5) alone — the exact waste memoization exists to fix.
What is Fibonacci Recursion?
fib(n) = fib(n-1) + fib(n-2), with fib(0) = 0 and fib(1) = 1 as base cases. Unlike factorial, which makes one recursive call per frame, Fibonacci makes two — which means the call tree branches instead of forming a single chain.
Why visualization helps
The branching is easy to state but hard to feel until you watch it — fib(5) calls fib(4) and fib(3), but fib(4)also calls fib(3) internally. LearnBug highlights every call, so the duplicate work is visibly there, not just something you're told is happening.
Why Fibonacci is different from factorial
Two calls per frame, not one
Factorial's call tree is a straight line — one call leads to one call. Fibonacci's is a real tree: each call spawns two more, until it branches into an exponential number of calls.
The same subtree gets rebuilt repeatedly
fib(3) is computed once inside fib(4)'s branch and again inside fib(5)'s direct branch — with no memory of the first computation, so it's fully redone from scratch.
The fix: remember what you've already computed
Caching each result the first time it's computed turns this from exponential into linear — that's exactly what the Dynamic Programming Fibonacci-Memoization lesson does next.
fib(5) — watch fib(3) get computed twice
fib(5) calls fib(4) first — the left branch dives all the way down
fib(4) calls fib(3), which calls fib(2), which calls fib(1) — a base case, returns 1 — then fib(2) also calls fib(0), another base case, returns 0. fib(2) = 1+0 = 1.
fib(3)'s second call, fib(1), is a base case — fib(3) = fib(2) + fib(1) = 1 + 1 = 2
This is the FIRST time fib(3) resolves — reached only through fib(4)'s branch so far. fib(4) still needs its own second call: fib(2), computed again from scratch.
fib(4) finishes: fib(3) + fib(2) = 2 + 1 = 3 — now fib(5) needs its OWN fib(3)
fib(4) is done and returns 3. fib(5)'s left branch is fully resolved. Now fib(5) makes its second top-level call: fib(3) — but this is a completely fresh call, with no memory of the fib(3) computed one step ago.
fib(3) resolves again (2nd time, identical work) — fib(5) = fib(4) + fib(3) = 3 + 2 = 5
The second fib(3) call redoes the exact same fib(2), fib(1), fib(0) calls as the first one — none of that work was reused. This duplicated subtree is the entire reason naive Fibonacci is O(2ⁿ) instead of O(n).
Return: fib(5) = 5 ✓ correct answer, but fib(3) was fully recomputed once for nothing
Naive recursive Fibonacci
def fib(n):
if n <= 1: # base cases: fib(0)=0, fib(1)=1
return n
return fib(n - 1) + fib(n - 2) # two branches — no memory between them
print(fib(5)) # 5Complexity Notes
Frequently asked questions
Why exactly is naive Fibonacci O(2ⁿ)?
Every call (except the base cases) makes exactly two more calls, so the total number of calls roughly doubles with each additional level of n — the classic shape of exponential growth. It's not precisely 2ⁿ (the real count follows the Fibonacci sequence itself), but it's exponential either way, which is the important part.
How does memoization fix this?
Store each fib(k) result in a dictionary the first time it's computed. The next time any branch asks for fib(k), return the cached value instantly instead of recomputing the whole subtree. This collapses the exponential tree down to exactly n unique computations — see the Dynamic Programming section's Fibonacci — Memoization lesson for the full walkthrough.
Why doesn't the call stack also grow exponentially?
Only one path through the tree is "in progress" on the call stack at any moment — Python fully finishes the left branch (popping those frames) before it even starts the right branch. So stack depth tracks the tree's height (n), not its total number of nodes (2ⁿ).
Is there a way to compute Fibonacci without recursion at all?
Yes — an iterative version with two running variables (a, b = b, a + b) computes fib(n) in O(n) time and O(1) space, no call stack and no cache needed. It's the fastest practical approach for a single Fibonacci value; memoized recursion mainly wins when you're calling fib() repeatedly across a larger program.
Watch the branches split — and one of them repeat
Paste your Fibonacci function into LearnBug and see every call in the tree, including the duplicates.