Run it: Memoisation in code
The same recurrence three ways with call counts, then cache_info() showing the hit rate. Then the two conditions broken on purpose. An impure task and an unhashable input.
The manual version, and why to know it
Note memo=None rather than memo={}. A mutable default input is created once, at task definition, and shared by each call that does not supply one. So yields leak between unrelated invocations. It happens to work for a pure task like Fibonacci and is a genuine bug broadly, and interviewers watch for it.
The manual version is worth knowing since it is what you write when the cache needs to be inspected, bounded by a custom rule, or shared by name between calls.
When memoisation applies
Three conditions, and all three are needed:
The task is pure — same inputs always give the same yield, with no side effects. Memoising a task that reads a store or the clock returns stale answers.
Inputs are hashable. Lists and dictionaries cannot be cache keys. Turn to tuples or frozensets.
Subproblems repeat. Caching a task called once per distinct input adds cost for nothing.
That third point is the one that separates memoisation from a general speed-up. It is just 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 vals an rapid count of times. Memoisation does not make each call faster. It makes the repeated ones disappear. So the work drops to the count of distinct subproblems.
This is dynamic programming from the top down. The bottom-up table computes the same vals in a loop with no call stack. Same cost, and see dynamic programming for both ways side by side.
The two conditions
The task must be pure. Same inputs, same answer, no side effects. Caching a task that reads a file or the clock returns a stale answer for good. And the bug looks like the data being wrong rather than the cache being wrong.
The inputs must be hashable. They turn dictionary keys, so a list input raises. That is why cached tasks 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 too 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 really ship.
lru_cache in practice
cache_info() is the nearly useful part: it tells you whether the cache is earning its place. A hit rate near zero means the inputs rarely repeat and the decorator is pure cost.
Four constraints worth knowing:
Inputs must be hashable. lru_cache keys on the input tuple. So a list input raises TypeError.
Keyword and positional inputs key else. f(1) and f(x=1) are separate cache entries. This 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.
Ways 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 edge is that just the subproblems really needed are computed — which matters when the state space is large and sparsely visited. Tabulation's gains are no recursion limit and easier space reduction.
Write memoisation first, since the recurrence is the part you have to think about. Turn 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.
- Store query caching. Same query, same yield, until the data changes.
- Costly pure steps — parsing, compiling regular terms (
re.compile is it 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 plan in time serves stale data, and "when does this turn wrong?" is the question to ask before adding one. For pure tasks the answer is never, which is why memoisation is the easy case.
For the underlying ideas, see dynamic programming, recursion and dictionaries.