Time–space trade-offs with memoization
Spend memory on a cache to turn exponential recursion into linear work.
On this page
Recursion and dictionaries.
- Spend memory on a cache to turn exponential recursion into linear work.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
Many algorithms can trade memory for speed. Memoization stores the result of a function for each distinct argument so a repeated call returns the stored answer instead of recomputing it. It helps when a recursive solution solves the same subproblems again and again.
The naive recursive Fibonacci function makes two calls for every n >= 2. The call tree has Θ(φⁿ) nodes, where φ ≈ 1.618, so the work grows exponentially. Fibonacci(20) needs 21,891 calls even though only 21 different arguments exist. With a cache each distinct argument is computed once, so the number of calls drops to 39 and the work is O(n).
The price is O(n) memory for the cache, plus recursion depth O(n). This is the same idea as top-down dynamic programming. Whenever you analyse a speed-up, also record what resource it spends, here space, and check that the saved time is worth it.
Code example
calls = 0
def fib_slow(n):
global calls
calls += 1
return n if n < 2 else fib_slow(n - 1) + fib_slow(n - 2)
def fib_memo(n, cache):
global calls
calls += 1
if n in cache:
return cache[n]
cache[n] = n if n < 2 else fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
return cache[n]
calls = 0
slow = fib_slow(20)
slow_calls = calls
calls = 0
fast = fib_memo(20, {})
fast_calls = calls
print(slow, slow_calls)
print(fast, fast_calls)
assert slow == fast6765 21891 6765 39
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
calls = 0 def fib_slow(n): global calls calls += 1 return n if n < 2 else fib_slow(n - 1) + fib_slow(n - 2) def fib_memo(n, cache): global calls calls += 1 if n in cache: return cache[n] cache[n] = n if n < 2 else fib_memo(n - 1, cache) + fib_memo(n - 2, cache) return cache[n] calls = 0slow = fib_slow(20)slow_calls = callscalls = 0fast = fib_memo(20, {})fast_calls = callsprint(slow, slow_calls)print(fast, fast_calls)assert slow == fastFollow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Each call below 2 returns directly; every other call spawns two more, so the same values are recomputed many times. | — | — | |
| The memoized version checks the cache first and returns a stored answer in O(1). | — | — | |
| Without caching, fib(20) needs 21,891 calls. | slow_calls = 21891 | 6765 21891 | |
| With caching, only 39 calls are made for the same answer. | fast_calls = 39 | 6765 21891 6765 39 |
Behind the scenes
How Python processes this code
Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.
Cost and common mistakes
fib_slow makes Θ(φⁿ) calls. fib_memo does O(n) work and uses O(n) space for the cache and the call stack.
- A cache that grows without bound can exhaust memory. Real programs may need a size limit or an eviction policy.
- Memoization is only valid for pure functions: the result must depend only on the arguments.
- Very deep recursion can overflow the call stack. For large n an iterative bottom-up loop avoids the depth problem.
Try it yourself
How many calls does fib_memo(10, {}) make?
Reveal answer and reasoning
19. There is one top-level call plus two child calls for each of the nine values from 2 to 10; every later request for a smaller value is a cache hit that still counts as a call. So 1 + 2 × 9 = 19.