What is Memoization

Memoization is the practice of storing the results of expensive function calls so that when the same inputs occur again, the cached result is returned immediately. The name comes from "memo" — writing down an answer so you don't have to work it out twice.

How it works

Consider the naive recursive Fibonacci function:

fib(5) calls fib(4) and fib(3)
fib(4) calls fib(3) and fib(2)
fib(3) calls fib(2) and fib(1)   ← fib(3) computed twice
fib(2) calls fib(1) and fib(0)   ← fib(2) computed three times

Without memoization, fib(n) makes roughly 2^n calls — exponential growth. For fib(50), that is over a trillion redundant computations.

With memoization, the function checks a cache (typically a hash map or array) before computing:

1. Has this input been seen before? Return the cached result.
2. Otherwise, compute the result, store it in the cache, and return it.

fib(5) → not cached, compute: fib(4) + fib(3)
fib(4) → not cached, compute: fib(3) + fib(2)
fib(3) → not cached, compute: fib(2) + fib(1)
fib(2) → not cached, compute: 1. Cache it.
fib(1) → base case: 1
fib(3) → cached! Return immediately.
fib(5) → done in 5 lookups, not 15+ calls.

This drops the complexity from O(2^n) to O(n) — each subproblem is computed exactly once and looked up every subsequent time.

Memoization is sometimes called top-down dynamic programming because it starts with the original problem and recurses downward, caching along the way. Dynamic programming in its bottom-up form builds the table from the smallest subproblems upward. Both eliminate redundant work; they differ in direction.

The tradeoff is space. Memoization uses O(n) memory for the cache. For most problems this is a good trade — exchanging memory for an exponential speedup.

Why it matters

Memoization turns impractical recursive algorithms into efficient ones. It applies whenever a problem has overlapping subproblems — the same inputs are computed multiple times. Fibonacci, shortest paths, string matching, and many optimization problems all benefit. Recognizing when to add memoization to a recursive solution is one of the most important skills in algorithm design.

See How Recursion Works for the full progression from naive recursion to memoized solutions.