Loading algorithms…

Loading visualizer…

Algorithms/Dynamic Programming/Fibonacci (Memoization)

Fibonacci — Naive vs. Memoized

The canonical DP intro. Naive recursion calls fib(k) exponentially many times; a single cache collapses overlapping subproblems to O(n).

Dynamic ProgrammingMemoizationRecursion TreeTop-Down
fib(n)target
fib(5) = 5
Naive callsO(2ⁿ)
15
Memoized callsO(n)
9
Speed-upnaive ÷ memo
1.7×
1 / 20
Speed
5naive capped at 8 (exponential blowup above)

Naive fib(5)

Recomputes every subproblem — exponential blowup.

calls: 0
15 nodes
drag · scroll · dbl-click to fit · keys: + − 0
100%
5=54=33=22=11=10=01=12=11=10=03=22=11=10=01=1
Legend:active callopen framereturned
CALLStep 1

Naive recursion: fib(5) starts. The recursion tree explodes because fib(k) is computed independently for every node — exponential time.

fib-naive.js
1function fibNaive(n) {
2 if (n < 2) return n; // base case
3 return fibNaive(n - 1)
4 + fibNaive(n - 2);
5}

Memoized fib(5)

Caches every computed value — linear in n.

calls: 9
No calls yet. Press Play or step forward.
Cache is empty.
CALLStep 1

Memoized recursion: fibMemo(5) starts with an empty cache. Every new n will be computed once and stored.

fib-memo.js
1const memo = new Map();
2function fibMemo(n) {
3 if (n < 2) return n; // base case
4 if (memo.has(n)) return memo.get(n); // hit
5 const v = fibMemo(n - 1)
6 + fibMemo(n - 2);
7 memo.set(n, v); // cache
8 return v;
9}

Naive vs. memoized — the punchline

Same Fibonacci number, two implementations. Memoization collapses the overlapping subproblems.

Naive calls
15
Memoized calls
9
Naive ÷ Memo
1.7×
Memoization turns fib(n) from O(2ⁿ) into O(n).

Algorithm Explanation

Fibonacci is the classic introduction to dynamic programming. Defined recursively as fib(n) = fib(n−1) + fib(n−2) with base cases fib(0) = 0 and fib(1) = 1, it looks innocent — until you compute it naively and discover the call count explodes exponentially.

⚙️ Why Naive Is Exponential

Every call to fib(k) spawns two new calls. Most of those calls re-compute the same values over and over: fib(2) is computed at least 5 times in fib(7). The recursion tree has roughly 2·F(n+1) − 1 nodes — exponential.

// Recursion tree for fib(5) — 15 nodes
fib(5)
├── fib(4)
│ ├── fib(3)
│ │ ├── fib(2)
│ │ │ ├── fib(1) → 1
│ │ │ └── fib(0) → 0
│ │ └── fib(1) → 1
│ └── fib(2) // recomputed!
└── fib(3) // recomputed!

💾 Memoization

The fix is to cache every computed value. The first time fib(k) is computed, store the answer. Every subsequent call is an O(1) lookup. The recursion tree collapses from exponential to linear: each unique k is computed once.

🎯 Memoization = top-down DP. It uses recursion but stores subproblem results so they're never recomputed. The alternative is bottom-up tabulation: iteratively fill an array from fib(0) up to fib(n). Same time complexity, no recursion overhead, no stack risk.

⚖️ Naive vs. Memoized vs. Bottom-up

Naive recursion
  • O(2ⁿ) time, O(n) stack.
  • Re-computes the same subproblems repeatedly.
  • Easy to write, hard to use at scale.
  • Stack overflow around n = 10⁴ on most runtimes.
Memoized (top-down DP)
  • O(n) time, O(n) space (cache + stack).
  • Recursion + cache lookup.
  • Great when only a few subproblems are needed.
  • Closest to the natural recursive definition.
Bottom-up tabulation
  • O(n) time, O(1) space (just last two values).
  • No recursion, no stack overhead.
  • Cache-friendly, predictable.
  • Preferred for hot loops and embedded systems.
←Previous Algorithm
Linear Search
SearchingO(n)
Next Algorithm→
0/1 Knapsack
O(n·W)Dynamic Programming

Memoization trades a tiny bit of memory for a massive reduction in redundant work — the very essence of dynamic programming.