Run it
The same recurrence three ways with call counts, then cache_info() showing the hit rate, then the two conditions broken on purpose — an impure function and an unhashable argument.
The manual version, and why to know it
Note memo=None rather than memo={}. A mutable default argument is created once, at function definition, and shared by every call that does not supply one — so results leak between unrelated invocations. It happens to work for a pure function like Fibonacci and is a genuine bug in general, and interviewers watch for it.
The manual version is worth knowing because it is what you write when the cache needs to be inspected, bounded by a custom rule, or shared explicitly between calls.
When memoisation applies
Three conditions, and all three are required:
The function is pure — same arguments always give the same result, with no side effects. Memoising a function that reads a database or the clock returns stale answers.
Arguments are hashable. Lists and dictionaries cannot be cache keys; convert to tuples or frozensets.
Subproblems repeat. Caching a function called once per distinct argument adds overhead for nothing.
That third point is the one that separates memoisation from a general speed-up. It is exactly the "overlapping subproblems" condition of dynamic programming — memoisation is top-down dynamic programming.
| Problem | Overlapping subproblems | Memoisation helps |
|---|
| Fibonacci | Heavily | Enormously |
| Edit distance | Yes | Yes |
| Merge sort | No — independent halves | No |
| Binary search | No | No |
| Grid paths | Yes | Yes |
Why it works at all
Naive recursion on overlapping subproblems recomputes the same values an exponential number of times. Memoisation does not make each call faster; it makes the repeated ones disappear, so the work drops to the number of distinct subproblems.
This is dynamic programming from the top down. The bottom-up table computes the same values in a loop with no call stack — same complexity, and see dynamic programming for both directions side by side.
The two conditions
The function must be pure. Same arguments, same answer, no side effects. Caching a function that reads a file or the clock returns a stale answer forever, and the bug looks like the data being wrong rather than the cache being wrong.
The arguments must be hashable. They become dictionary keys, so a list argument raises. That is why cached functions take tuples where you might expect lists — the constraint comes from the cache, not the algorithm.
What lru_cache adds
@lru_cache(maxsize=None) is an unbounded dictionary and is what you want for a recursion. A finite maxsize evicts least-recently-used entries, which matters when the key space is large and unbounded — an in-memory cache with no eviction is a memory leak with good manners.
It also gives you cache_info() for hits and misses, and cache_clear(). functools.cache is the unbounded alias added in 3.9. Mention that a manual dict is fine and the decorator is what you would actually ship.
lru_cache in practice
cache_info() is the practically useful part: it tells you whether the cache is earning its place. A hit rate near zero means the arguments rarely repeat and the decorator is pure overhead.
Four constraints worth knowing:
Arguments must be hashable. lru_cache keys on the argument tuple, so a list argument raises TypeError.
Keyword and positional arguments key differently. f(1) and f(x=1) are separate cache entries, which doubles memory and halves the hit rate if callers are inconsistent.
maxsize=None never evicts. On unbounded input that is a memory leak; a bounded size is safer in long-running processes.
Methods keep self in the key, so instances are held alive by the cache — a real source of leaks. cachetools or an explicit per-instance dictionary avoids it.
Memoisation against tabulation
Two ways to write the same dynamic programming solution.
| | Memoisation (top-down) | Tabulation (bottom-up) |
|---|
| Style | Recursive plus a cache | Iterative, fills a table |
| Computes | Only the states reached | All states |
| Recursion limit | Yes — about 1,000 frames | No |
| Space optimisation | Harder | Often easy |
| Easier to write | Usually | Usually not |
Memoisation's advantage is that only the subproblems actually needed are computed — which matters when the state space is large and sparsely visited. Tabulation's advantages are no recursion limit and easier space reduction.
Write memoisation first, because the recurrence is the part you have to think about. Convert to tabulation if you hit Python's recursion limit or need the O(1) space version.
Where it is used beyond interviews
- Web response caching. Keyed on the request, with a TTL.
- Database query caching. Same query, same result, until the data changes.
- Expensive pure computations — parsing, compiling regular expressions (
re.compile is itself cached), rendering templates. - Property caching —
functools.cached_property computes once per instance. - API clients caching immutable lookups such as currency codes or country lists.
And the counterpart: invalidation is the hard part. A cache with no invalidation strategy eventually serves stale data, and "when does this become wrong?" is the question to ask before adding one. For pure functions the answer is never, which is why memoisation is the easy case.
Questions people ask
Why memo=None instead of memo={}? A mutable default is created once at definition and shared across calls.
Is lru_cache thread-safe? Yes, its bookkeeping is — and the wrapped function may still be called twice concurrently for the same key.
What if arguments are unhashable? Convert to tuples or frozensets, or hash a canonical serialisation.
How large should maxsize be? Large enough for the working set, small enough to bound memory. Use cache_info() to check the hit rate.
Does it help every recursive function? Only when subproblems repeat. Merge sort gains nothing.
What is cached_property? A decorator computing a property once per instance and storing the result on the instance.
Recap in one screen
- Store results keyed on arguments; return the stored value on a repeat call.
@lru_cache or @cache turns exponential recursion into linear in one line.- Requires a pure function, hashable arguments, and genuinely repeating subproblems.
- Never use a mutable default argument as the cache — it is shared across all calls.
- Memoisation is top-down dynamic programming; tabulation is the iterative form without a recursion limit.