Overview
Top-down memoization keeps the natural recursive structure but adds a cache: the first time a subproblem is solved, its answer is stored, and every later request returns the cached value instead of recomputing it.
Applied to Fibonacci, memoization is transformative: the exponential naive recursion collapses to linear time because each value fib(k) is computed exactly once, then reused.
How Memoization works
- Before computing fib(n), check whether the cache already holds it.
- On a cache hit, return the stored value immediately — no further recursion.
- On a miss, recurse into fib(n−1) and fib(n−2) as usual to get the value.
- Store the freshly computed result in the cache before returning it.
When to use it
- Dynamic programming problems with overlapping subproblems (Fibonacci, coin change, grid paths).
- Retrofitting speed onto an existing clear recursive solution with minimal code change.
- Prefer bottom-up tabulation when recursion depth risks a stack overflow.
Complexity analysis
With memoization each of the n distinct subproblems is solved once and cheaply reused, so Fibonacci runs in O(n) time. The cache and the recursion stack each hold O(n) entries, giving O(n) space — a dramatic improvement over the naive O(φ^n).
Frequently asked questions
What is the difference between memoization and tabulation?
Memoization is top-down: it recurses and caches results lazily as they are needed. Tabulation is bottom-up: it fills a table iteratively from the base cases. Both reach O(n) for Fibonacci.
Does memoization change the algorithm's answers?
No. It only avoids repeated work; the returned values are identical to the naive recursion. It is a pure performance optimization that trades memory for time.