The Core Idea
Trading Memory for Time
Memoization stores the result of a function call keyed by its input, so that if the same input occurs again, the cached answer is returned instantly instead of recomputing it. It's the 'top-down' form of dynamic programming: you write the natural recursive solution first, then add a cache that intercepts repeated calls.
The technique only helps when a recursive solution actually calls itself with the same arguments multiple times — this is called having overlapping sub-problems. If every recursive call has genuinely unique arguments (no repeats), memoization adds overhead with zero benefit.
💡 Memory Trick
Picture a student solving the same homework problem for the third time because they forgot they'd already worked it out on scratch paper twice before. Memoization is simply keeping that scratch paper — the instant the same problem appears again, you glance at your notes instead of re-deriving the answer from zero.
The Classic Example
Fibonacci: From O(2ⁿ) to O(n)
1
The Naive Recursive Version
fib(n) = fib(n-1) + fib(n-2) looks clean, but it recomputes the same sub-values repeatedly — fib(5) calls fib(4) and fib(3), but fib(4) itself calls fib(3) again, duplicating work. This redundancy compounds exponentially, giving O(2ⁿ) time.
Example: computing fib(30) naively requires over 2.7 million function calls, most of them wasted recomputation.
2
Add a Cache
Before computing fib(n), check whether n is already a key in a cache (often a dictionary or array). If so, return the cached value immediately. If not, compute it as usual, then store the result in the cache before returning.
Example: cache = {}; if n in cache: return cache[n] — this single check eliminates all redundant recomputation.
3
The Complexity Result
With memoization, each unique value of n is computed exactly once — after that, every repeated call is an O(1) cache lookup. This drops Fibonacci from O(2ⁿ) to O(n), a difference so large that memoized fib(50) runs instantly while naive fib(50) would take an impractically long time.
Example: fib(50) naive ≈ trillions of operations; fib(50) memoized ≈ 50 operations.
Beyond Fibonacci
Recognizing When to Reach for Memoization
The signal that memoization applies is recursion where the same sub-problem gets requested from multiple different call paths — common in problems like counting paths in a grid, edit distance between two strings, longest common subsequence, and coin change. Whenever you notice a recursive solution 'looks slow' and you can identify that it's solving the same smaller case repeatedly, memoization is the first tool to reach for.
Memoization is contrasted with 'tabulation' (bottom-up dynamic programming), which builds the answer iteratively from the smallest sub-problem upward instead of recursing downward with a cache. Both achieve the same complexity improvement; memoization tends to be more intuitive to write since it mirrors the natural recursive definition, while tabulation avoids recursion's call-stack overhead entirely.
🖥️ Applied Scenario
You've written a recursive function to count the number of distinct ways to climb a staircase of n steps (taking 1 or 2 steps at a time), and it's taking far too long for n = 40.
1
You trace through the recursion and notice that ways(38) is being computed independently from both ways(39) and ways(40)'s call trees — the exact same sub-problem, solved from scratch each time it's reached.
2
You add a dictionary cache: before computing ways(n), check if n is already a cached key, and return that cached value immediately if so.
3
After computing ways(n) for the first time, you store the result in the cache before returning it, so any future call with that same n is instant.
4
Conclusion: ways(40), which was previously computationally infeasible due to exponential redundant recursion, now completes instantly because each unique step count is only ever computed once.
📌 Exam Application
Exam questions often give you a naive recursive function and ask you to add memoization, or to state its time complexity before and after. The expected answer identifies which sub-problems overlap (are called more than once from different paths) and explains that caching those specific results is what converts exponential time into polynomial or linear time — not memoization as a vague 'speed it up' gesture.
⚠️ Most Common Memoization Mistakes
The most common mistake is memoizing a recursive function whose calls don't actually overlap — adding a cache in that case adds memory overhead and lookup cost with no speed benefit, since every cached entry is only ever checked once. Another frequent error is forgetting to key the cache by all relevant arguments — if a function takes two parameters but you only cache by one, you'll return wrong cached results for calls that share one argument but differ in the other.
✓ Quick Self-Test
Can you explain, using the Fibonacci recursion tree, exactly which calls are being needlessly repeated without memoization? Can you write, from memory, the two extra lines of code that turn a naive recursive function into a memoized one?
Next Lesson
Sliding Window Technique
→
← All Algorithms Lessons