vizlearn

Memoisation: caching with a dictionary

Interview QuestionsBy Updated

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.

Overview

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.

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."

Memoisation: caching with a dictionary

How would you speed up a recursive function that recomputes the same values? What does functools.lru_cache do?

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.

Run it in Python

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.

memoisation.pyPython 3
Output
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
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.
INTERVIEW · vizlearn.in/interview/memoisation-with-a-dictionary.html
More in Interview
InterviewImplement a hash map from scratchInterviewGroup records and invert a dictionaryInterviewWhy are Python strings immutable?InterviewWhat does slicing a string cost?
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.
About VizLearnGitHubLinkedInContact