fib(5) = 5 — three approaches

🚫 Naive RecursionO(2ⁿ)

no cache — recomputes everything

15 calls

💾 Memoization (top-down)O(n)

cache computed values

9 calls

✅ Bottom-up DPO(n)*

*O(1) space keeping last 2

~6 iters

Naive fib(5): 15 function calls, exponential redundancy.

fib(5) calls fib(4) AND fib(3) — the call tree doubles every level = O(2^n).

15 calls

1 / 10

SPD0.5×

click to pause · hover for controls · fullscreen for more

Fibonacci

Why naive recursion is O(2ⁿ) — and how memoisation fixes it

Visual by thisgirltech

BeginnerConcept

The Fibonacci sequence is simple: fib(n) = fib(n-1) + fib(n-2), with base cases fib(0)=0 and fib(1)=1. But the naive recursive implementation hides a trap — it recomputes the same values over and over, leading to exponential time complexity.

This animation shows both approaches side by side: naive recursion (O(2ⁿ)) and memoised recursion (O(n)). The call counter makes the difference impossible to ignore.

Naive is O(2ⁿ)

Each call to fib(n) branches into two sub-calls. The call tree roughly doubles at every level, giving ~2ⁿ total calls. fib(30) = over a billion calls.

Memoisation is O(n)

Store each result the first time it's computed. Every future call is a cache hit — instant return. Only n+1 unique computations are ever needed.

Foundation of DP

Memoised Fibonacci is your first taste of dynamic programming — overlapping subproblems solved by caching. The same pattern applies to coin change, knapsack, and LCS.

TIP

Try running naive fib(7) vs memoised fib(7). Count the calls. The naive version makes 41 calls. Memoised makes 8. Same answer, radically different work.