Memoization
Memoization is an optimization technique that stores (caches) the results of expensive function calls and returns the cached result when the same inputs occur again, avoiding redundant computation in recursive algorithms. It is the top-down implementation strategy of dynamic programming, transforming an exponential-time naive recursion into polynomial time by ensuring each subproblem is solved only once. Memoization is used in recursive Fibonacci, shortest-path computations, and natural language parsing.
Worked Example
Problem
Compute the number of ways to climb a staircase with n=5 steps, taking 1 or 2 steps at a time. Use memoization.
Solution
Define ways(n) = ways(n-1) + ways(n-2), base cases: ways(0)=1, ways(1)=1. Without memo: ways(5) recomputes ways(3) multiple times (exponential). With memo (cache = {}): ways(5): cache miss → calls ways(4) + ways(3). ways(4): cache miss → calls ways(3) + ways(2). ways(3): cache miss → calls ways(2) + ways(1) = 2 + 1 = 3. Store cache[3]=3. ways(2): cache miss → calls ways(1) + ways(0) = 1 + 1 = 2. Store cache[2]=2. ways(4) = cache[3] + cache[2] = 3 + 2 = 5. Store cache[4]=5. ways(5) = cache[4] + cache[3] = 5 + 3 = 8. Store cache[5]=8.
Answer
ways(5) = 8. Memoization reduced time from O(2^n) to O(n) with O(n) cache space.
Memoization vs Tabulation (Bottom-Up DP)
| Aspect | Memoization (Top-Down) | Tabulation (Bottom-Up) |
|---|---|---|
| Direction | Recursive, start from target | Iterative, start from base |
| Subproblems solved | Only needed subproblems | All subproblems in order |
| Storage | Hash map or array | Array (more cache-friendly) |
| Overhead | Function call overhead | No recursion overhead |
| Code clarity | Closer to natural recursion | Requires explicit ordering |
| Stack overflow risk | Yes (deep recursion) | No |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Dynamic Programming
Dynamic Programming (DP) is an algorithmic paradigm that solves complex problems by breaking them into overlapping subproblems, solving each subproblem only once, and storing results to avoid redundant computation (memoization or tabulation). It applies when a problem exhibits two key properties: optimal substructure (optimal solution contains optimal solutions to subproblems) and overlapping subproblems. DP is used in sequence alignment, shortest-path problems, knapsack optimization, and compiler design.
Recursion
Recursion is a programming and mathematical technique in which a function calls itself with a smaller or simpler version of the original problem, progressing toward one or more base cases that terminate the chain of calls. Every recursive solution requires a base case (stopping condition) and a recursive case (self-referential reduction). Recursion is fundamental to tree traversal, divide-and-conquer algorithms, backtracking, and functional programming.
Divide and Conquer
Divide and Conquer is an algorithmic paradigm that recursively breaks a problem into two or more smaller subproblems of the same type until they become simple enough to solve directly, then combines their solutions to solve the original problem. The three phases are: Divide (split the problem), Conquer (solve subproblems recursively), and Combine (merge results). Famous examples include Merge Sort, Quick Sort, Binary Search, and the Fast Fourier Transform.
Coined by Donald Michie in 1968, from Latin memorandum ("something to be remembered"), via the English word "memo." The spelling deliberately omits the "r" to distinguish it from the ordinary English word "memorization." Michie introduced the term in the context of making machine learning programs more efficient.