Memoization · Dynamic programming

Memoization Cliff

Slider for fib(N); side-by-side call trees, naive vs memoized. Watch the exponential turn linear.

The same recursive function, with one tiny addition — caching the result of each sub-call. The naive version recomputes fib(k) for every value of k that appears in the recursion tree; the memoized version computes each fib(k) exactly once. The call count drops from exponential to linear. This is the entire idea of dynamic programming, in the smallest possible form.

Compute fib(5)Drag to 1–35

Naive recursion · O(2ⁿ)

function calls

Memoized · O(n)

6 unique values + 3 cache hits

The cliff

1.7×

More work the naive version does, for the same answer.

Naive — every subtree recomputed

f(5)

f(4)

f(3)

f(2)

f(1)

f(0)

f(1)

f(2)

f(1)

f(0)

f(3)

f(2)

f(1)

f(0)

f(1)

Memoized — cached values collapse to a single lookup

f(5)

f(4)

f(3)

f(2)

f(1)

f(0)

f(1)

f(2)

f(3)

f(n)compute (recurse)f(n)cache hit (no recursion)f(0)base case

What you’re seeing: the same algorithm, with one tiny addition — caching the result of each sub-call. The call count drops from exponential to linear. This is the entire idea of dynamic programming: identify the sub-problems your recursion already solves and stop solving them again. The technique scales: at n=50, naive needs ~32 billion calls; memo needs 99.

What’s happening under the hood

›Naive fib(n) has T(n) = T(n-1) + T(n-2) + 1 function calls — growing like Fibonacci itself, roughly 1.618ⁿ. fib(35) needs ~30 million calls.
›Memoized fib(n) computes each value once: n+1 unique values, plus ~n-1 cache hits = ~2n-1 total calls. fib(35) needs ~69 calls.
›Memoization is the canonical dynamic-programming optimization. Every DP problem in the textbook reduces to: identify the sub-problems, cache them, never recompute. The same principle drives prompt caching in LLM APIs (lesson 6-7 · cost engineering).

Dig deeper

Phase 1 · Functions

The concept you just explored is taught with full depth in the formal DURA curriculum.