Memoisation: caching with a dictionary

Put a dictionary in front of the function: if the arguments have been seen, return the stored answer. That collapses an exponential call tree into a linear walk without changing the recurrence at all. functools.lru_cache is this, with a size bound and thread safety.

Dicts, sets & hashingCoding problemMedium

Step through it

What to watch

  • Call counts diverge fast — the gap is exponential against linear.
  • The recurrence is identical in both versions.
  • The cache is what turns repeated subproblems into one lookup.

Say this out loud

"Memoise it - a dict keyed on the arguments. The recursion is unchanged; it just stops descending into subtrees it has already solved. In Python that's @lru_cache, which also bounds the size so it can't grow forever."

Overview

Memoisation caches results of function calls so repeated subproblems are computed once. It helps when inputs repeat and each result depends only on its arguments; a cache cannot fix an incorrect recurrence or excessive state space.

In this guide
  1. Run it: Memoisation in code
  2. The manual version, and why to know it
  3. When memoisation applies
  4. Why it works at all
  5. The two conditions
  6. What lru_cache adds
  7. lru_cache in practice
  8. Memoisation against tabulation
  9. Where it is used beyond interviews
  10. Sources and next steps

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.

1Python
Output
2Python
Output
3Python
Output
4Python
Output
5Python
Output

The manual version, and why to know it

6Python
Output

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.

ProblemOverlapping subproblemsMemoisation helps
FibonacciHeavilyEnormously
Edit distanceYesYes
Merge sortNo — independent halvesNo
Binary searchNoNo
Grid pathsYesYes

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

7Python
Output

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)
StyleRecursive plus a cacheIterative, fills a table
ComputesOnly the states reachedAll states
Recursion limitYes — about 1,000 framesNo
Space optimisationHarderOften easy
Easier to writeUsuallyUsually 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.

Sources and next steps

How the code works

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.

How the code works

  1. if n in cache: return cache[n]The entire optimisation. The recurrence below it is untouched — memoisation does not make calls faster, it removes the repeated ones.
  2. @lru_cache(maxsize=None)Unbounded, which is what a recursion wants. A finite size evicts least-recently-used entries and is what you want when the key space is large enough to be a leak.
  3. impure()Cached once and stale forever. The failure looks like wrong data rather than a wrong cache, which is why purity is stated as a precondition rather than a nicety.
  4. total([1, 2, 3])A TypeError: arguments become dictionary keys. That is why cached functions so often take tuples — the constraint comes from the cache, not the algorithm.

Change one thing

  • Call fib_plain(35). It is the same recurrence and it stops being a demonstration and starts being a wait.
  • Set maxsize=2 on fib_cached and check cache_info(). Eviction destroys the benefit for a recursion that revisits old values.

Where this runs

Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.

Check yourself

0 of 3

Answer without scrolling back up.

  1. Memoisation speeds up recursion by:

  2. Caching a function that reads the current time gives you:

  3. Why must a cached function's arguments be hashable?

Cheat sheet

Memoisation: caching with a dictionary

Cache recursive results in a dictionary to kill recomputation. Watch the call tree shrink from exponential to linear, then switch to lru_cache.

INTERVIEW · vizlearn.in/interview/memoisation-with-a-dictionary.html

About the author

Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.

Teaching a course with this? Individual teachers can use it freely; for a whole department or programme, see institutional licences.