Memoization & the Slot Filler
Tunebox Radio fills gaps between shows with station idents, and the scheduling screen shows how many different ident sequences could fill each gap. The obvious recursive count answers instantly for a 10-minute gap and freezes the app at 40. The recursion isn't wrong. It's answering the same questions millions of times. Memoization makes it remember.
The slow way: Fibonacci
Fibonacci is the smallest program with this disease. Count the calls:
21,891 calls to work out one number. Try a small one first:
calls = 0
def fib(n):
global calls
calls += 1
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
fib(5)
print(calls)Overlapping subproblems
Here is the call tree for fib(5):
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) f(1) f(0) f(1) f(0)
/ \
f(1) f(0)fib(3) is solved twice and fib(2) three times. Every level roughly doubles
the repeats, so the running time grows like φⁿ ≈ 1.618ⁿ. fib(40) makes
about 331 million calls. When a problem has
overlapping subproblems (the same smaller question keeps coming up) and
optimal substructure (the answer is built from answers to smaller
questions), it's a dynamic programming problem. The fix is to solve each
question once.
Memoize with a dict
Before computing, check whether you already know the answer. After computing, write it down:
Step through fib(4). The second time fib(2) is asked for, it comes straight
out of memo:
calls = 0
def fib(n, memo):
global calls
calls += 1
if n in memo:
return memo[n]
if n < 2:
return n
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]
fib(30, {})
print(calls)The cache key must hold everything that matters
A memo is only correct if the same key always means the same answer. Here the memo remembers answers for one set of ident lengths and serves them for a different set:
With 1- and 3-minute idents there are 3 ways to fill 4 minutes, so this should print 5 3. It prints 5 5, because the second call reads answers cached by the first.
❓ Cross-question: "Isn't memoization just caching?" Yes: a cache of a function's results, keyed on its arguments. That only works for a pure function, one whose answer depends on its arguments and nothing else. Read a global, or leave out an argument from the key, and the cache serves stale answers without any error.
functools.cache: memoization in one line
The standard library writes the dict for you. @cache (Python 3.9+) is shorthand
for @lru_cache(maxsize=None):
The cache stores arguments as dict keys, so every argument must be hashable:
from functools import cache
@cache
def total_minutes(lengths):
return sum(lengths)
print(total_minutes([3, 4]))Counting ways to fill a slot
With 1- and 2-minute idents, any fill of t minutes ends with either a 1-minute
ident (after a fill of t − 1) or a 2-minute ident (after a fill of t − 2).
So:
ways(t) = ways(t − 1) + ways(t − 2)ways(0) = 1, because there's exactly one way to fill nothing: play nothing.
That's Fibonacci again, and it's the same recurrence as climbing stairs one or two steps at a time.
For any list of lengths, the last ident can be any length L, so you add
up ways(t − L) over every length. That's your task.
Sequences or combinations?
1 + 2 and 2 + 1 are two different broadcasts, so count_fills counts
sequences. If you only care which idents you use, not their order, you're
counting combinations, and you need more state:
To count combinations directly, stop the recursion from picking an earlier
length after a later one. The state then needs a second number, which
lengths you may still use, so the memo key becomes (index, remaining).
General rule: the state is every argument that changes between calls.
The top-down recipe:
- Write the plain recursion. Get it correct on small inputs.
- Name the state: the arguments that change between calls.
- Cache on exactly that state, with a dict or
@cache.
| Version | Time | Space |
|---|---|---|
Plain recursive fib(n) |
O(φⁿ) ≈ O(1.618ⁿ) | O(n) call stack |
Memoized fib(n) |
O(n) | O(n) memo + stack |
Memoized count_fills(slot, lengths) |
O(slot · k) for k lengths | O(slot) |
| One memo lookup or store | O(1) average | none |
Coming from Java/JS: the memo is a
HashMap<Integer, Long>or a JSMap. One real difference: Python integers never overflow. Java'slongoverflows atfib(93), and a JS number stops being exact after 2⁵³, atfib(79). Python just keeps going.
Idioms & real-world patterns
A fresh cache per call
Decorate a nested function, and every call of the outer function gets a new cache. Inputs that never change, like an unhashable list, stay outside the key, and nothing leaks between calls. Here Tunebox promotes tracks on the home page, but never two neighbours in a row:
⚡ Advanced: the recursion limit
A cache hit returns immediately, but a cache miss still goes one frame deeper.
Python stops at about 1000 frames, so asking a cold cache for ways(5000) raises
RecursionError. The workaround is to warm the cache in small steps, so no single
call has far to fall:
Taken to its conclusion, filling answers from small t upward with no recursion
at all is tabulation, the next lesson.
⚡ Advanced: bounded caches
@lru_cache(maxsize=128) keeps only the 128 most recently used answers. That's
right for a web handler seeing endless new arguments, and wrong for DP, where
evicting a subproblem means solving it again. fib.cache_clear() empties a cache
between runs.
🎯 Your turn
Write count_fills(slot, lengths). It counts the sequences of idents (any
length in lengths, repeats allowed, order matters) whose lengths add up to
exactly slot minutes. count_fills(0, lengths) is 1: the empty sequence.
count_fills(4, [1, 2])→5(1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2)count_fills(60, [1, 2])→2504730781961, which the checker only waits for if you memoize
Hint: ways(t) = sum(ways(t − L) for L in lengths if L <= t), with ways(0) = 1.
Cache on t.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green means this piece of the app is built. ✅