# Memoization Explained > How caching a pure function's return value by its arguments lets you skip redoing the same expensive work twice, and where that trick quietly breaks. --- # Memoization Explained A pure function called twice with the same arguments does the same work twice and produces the same answer twice - if that work is expensive, the second call is pure waste, since you already know the answer but made the function recompute it anyway. Memoization is the fix: remember the answer the first time, keyed by the arguments, and hand back the memory instead of redoing the work. This guide covers the idea using the classic slow example, how to implement it, and where it backfires. ## How to read this Phase 1 introduces the core idea through naive recursive Fibonacci - the textbook case where the same subproblem gets solved an exponential number of times. Phase 2 covers the actual mechanics: a cache keyed by arguments, and the tools (decorators, higher-order functions) that wrap a function in that cache for you. Phase 3 is the clear-eyed tradeoff - unbounded memory, silently wrong answers when the function isn't really pure, and how memoization differs from a general-purpose cache like Redis. ## The phases 1. [Don't compute the same answer twice](01-dont-compute-twice.md) - the core idea, with exponential recursive Fibonacci as the motivating example. 2. [How to actually implement it](02-how-to-implement-it.md) - a cache keyed by arguments, decorators, and the purity requirement. 3. [When it backfires](03-when-it-backfires.md) - unbounded memory, false purity, and memoization vs. general caching. --- # Don't compute the same answer twice Take a function that always gives the same output for the same input - no randomness, no reading a clock, no touching a database. Call it `f(5)` and you get a value back; call it again a minute later and you get exactly the same value, guaranteed, because nothing the function depends on has changed. So why did the second call redo all the work to arrive at an answer you already had? **Memoization** is remembering that answer: the first time you call `f(5)`, you compute it and stash the result in a lookup keyed by the argument, `5`. The next time anything calls `f(5)`, you hand back the stashed value instead of running the function body again - same input, same output, computed once. > If a function always gives the same answer for the same input, computing that answer twice is pure waste - you're spending time to relearn something you already knew. ## The classic slow example: recursive Fibonacci The Fibonacci sequence is a textbook example precisely because the naive recursive version is dramatically, needlessly slow - and it's slow for exactly the reason memoization fixes. Each number in the sequence is the sum of the two before it: `fib(n) = fib(n-1) + fib(n-2)`. ```js function fib(n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } ``` *What just happened:* this reads like a direct translation of the math, and it is - but look at what `fib(n - 1)` and `fib(n - 2)` each do internally. `fib(n - 1)` calls `fib(n - 2)` and `fib(n - 3)`, while `fib(n - 2)` calls `fib(n - 3)` and `fib(n - 4)` - so `fib(n - 3)` gets computed by *both* branches, and each of those recomputes its own overlapping subproblems too. ```text fib(5) / \ fib(4) fib(3) / \ / \ fib(3) fib(2) fib(2) fib(1) / \ / \ / \ fib(2) fib(1) ... ... ... ... ``` *What just happened:* `fib(3)` appears twice in this tree at depth 2 alone, and `fib(2)` appears three times. Every one of those calls redoes the exact same work as the others with the same argument, and each of those calls re-triggers its own duplicated subcalls. The result is a tree of calls that grows exponentially with `n`, even though there are only `n` distinct answers to compute. ## Watching the blowup The numbers make the problem concrete. Here's roughly how many times `fib()` gets called, naively, for increasing `n`: ```text fib(10) -> 177 calls fib(20) -> 21,891 calls fib(30) -> 2,692,537 calls fib(40) -> 331,160,281 calls ``` *What just happened:* going from `n=10` to `n=40` - four times larger input - turned 177 calls into over 331 million. That's not linear, or even polynomial: naive recursive Fibonacci does roughly `2^n` work for an input of size `n`, yet there are only 41 *distinct* answers between `fib(0)` and `fib(40)`. You're doing 331 million calls to learn 41 numbers you'd only need to learn once each. ## What memoization changes Now hold onto the fix conceptually, before the mechanics in Phase 2: keep a lookup table from `n` to `fib(n)`. Before computing `fib(n)`, check the table - if it's already there, return it immediately (no recursion, no repeated subtree); if it isn't, compute it the normal way and write the answer into the table before returning. ```text fib(5) called, not in table -> needs fib(4) and fib(3) fib(4) called, not in table -> needs fib(3) and fib(2) fib(3) called, not in table -> needs fib(2) and fib(1) fib(2) called, not in table -> needs fib(1) and fib(0) -> computes, stores fib(2) fib(1), fib(0) -> base cases, no computation needed fib(3) resumes -> already has fib(2) and fib(1) -> computes, stores fib(3) fib(4) resumes -> already has fib(3) and fib(2) -> computes, stores fib(4) fib(5) resumes -> already has fib(4) and fib(3) -> computes, stores fib(5) ``` *What just happened:* every distinct value of `n` from 0 to 5 got computed exactly once. The second time anything asks for `fib(3)`, it's a table lookup, not a re-triggered subtree of recursive calls. This turns the `2^n` explosion into something that does roughly `n` total units of work - a change from millions of calls to dozens, for the same input. ## The mental model to keep One picture: **a function plus a notebook.** Before doing the work, check the notebook for this exact input - if it's written down, read the answer and stop; if not, do the work, then write the answer down before returning it. The notebook is the whole trick - everything in Phase 2 is different ways of building and managing it automatically instead of by hand. ```quiz [ { "q": "In naive recursive Fibonacci, why does fib(30) end up making millions of calls when there are only 31 distinct answers to compute?", "choices": [ "The function has a bug that causes infinite recursion", "The same subproblems (like fib(3) or fib(10)) get recomputed repeatedly across different branches of the call tree", "JavaScript recursion is inherently slower than loops", "Fibonacci numbers require floating-point precision that slows down each call" ], "answer": 1, "explain": "Overlapping subproblems are the whole issue: fib(n-1) and fib(n-2) both eventually call fib(n-3), fib(n-4), and so on, so the same answer gets rederived over and over." }, { "q": "What is the core mechanism of memoization?", "choices": [ "Running the function on a faster machine", "Storing a function's result keyed by its arguments, so a repeated call with the same arguments returns the stored result instead of recomputing", "Rewriting recursive functions as loops", "Compressing the function's return value to save memory" ], "answer": 1, "explain": "Memoization is a lookup: check whether this exact input's answer is already known before doing the work, and store the answer once it's computed." }, { "q": "What requirement must a function meet for memoization to give correct results?", "choices": [ "It must be recursive", "It must always return the same output for the same input, with no other side effects it depends on or produces", "It must run in under one millisecond", "It must only take numeric arguments" ], "answer": 1, "explain": "Memoization assumes the same input always deserves the same cached answer. That's only true for pure functions - Phase 2 covers this requirement directly, and Phase 3 covers what breaks when it's violated." } ] ``` Watch it animated: [memoization](/explainers/Memoization.dc.html) --- # How to actually implement it The notebook from Phase 1 - check before computing, write down after - can be built by hand, but you'll rarely need to. Most languages give you a ready-made wrapper that turns any pure function into a memoized one with a single line. Here's the by-hand version first, so the wrapper isn't a black box, then the standard tools. ## Building the notebook by hand The notebook is a lookup keyed by arguments - a map, dictionary, or object, depending on your language. Wrap the function so every call checks the map first. ```js function memoizedFib(n, cache = {}) { if (n in cache) return cache[n]; // check the notebook if (n <= 1) return n; const result = memoizedFib(n - 1, cache) + memoizedFib(n - 2, cache); cache[n] = result; // write down the answer return result; } ``` *What just happened:* `cache` is the notebook, keyed by `n`. The first line checks it - if this `n` has already been solved, return the stored answer immediately, no further recursion; if it's missing, the function does the real work and writes the answer into the cache before returning. Every distinct `n` gets computed exactly once, no matter how many times it's asked for across the whole call tree. The argument becomes the key. If a function takes multiple arguments, the key is typically all of them combined - often as a string like `"3,7"` for arguments `3` and `7`, since most map/dictionary types need a single hashable key rather than a raw list of arguments. ## Decorators and higher-order functions Writing the cache-check-and-store logic by hand for every function you want to memoize gets repetitive fast, and it clutters the function's real logic with bookkeeping. The standard move is to let a **decorator** (Python) or a **higher-order function** (JavaScript and most other languages) do that wrapping for you - you write the plain function, and a small piece of reusable code adds the caching behavior around it. Python's standard library ships this as `functools.lru_cache`: ```python from functools import lru_cache @lru_cache(maxsize=None) def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2) ``` *What just happened:* the function body is exactly the naive, slow-looking version from Phase 1 - no cache dictionary, no manual lookup. The `@lru_cache` line above it does all of that automatically: every call gets checked against an internal cache keyed by its arguments before the function body ever runs, so you get the notebook behavior without writing the notebook logic yourself. ("LRU" stands for least-recently-used, which matters for Phase 3.) React's `useMemo` is the same underlying idea applied to a specific problem: avoiding an expensive recalculation on every render. ```jsx const sortedItems = useMemo(() => { return expensiveSort(items); }, [items]); ``` *What just happened:* `expensiveSort(items)` only re-runs when `items` changes between renders - that's the array on the second line, called the dependency list. If the component re-renders for an unrelated reason (a different piece of state changed) and `items` is the same reference it was last time, React hands back the previously computed `sortedItems` instead of re-sorting. Same principle as `lru_cache`, adapted to "the arguments" meaning "the values in this dependency list" rather than literal function parameters. ## The hard requirement: purity None of this works correctly unless the function is **pure** - the same input always produces the same output, and the function has no side effects it relies on or creates. This isn't a style preference; it's the load-bearing assumption memoization is built on. ```text pure (safe to memoize): function square(n) { return n * n; } -> square(4) is always 16, forever, no matter what else is happening not pure (unsafe to memoize): function getDiscount(userId) { return database.lookupDiscount(userId); } -> the database row for userId can change between calls ``` *What just happened:* `square` only depends on its argument, so caching `square(4) = 16` is always correct - there's no way for that answer to become wrong later. `getDiscount` looks like a function with one argument, but its real answer depends on the database row behind the scenes, which can change independently of `userId` - memoizing it would mean returning a discount that used to be true, silently, forever, even after the real value changed. The function signature doesn't tell you which category something falls into; you have to know what it depends on. > A memoized function is only as trustworthy as the purity of the function underneath it. Cache a pure function and you get free speed with no downside. Cache an impure one and you get a fast, confidently wrong answer. ## The mental model to keep Memoizing a function is really two decisions bundled into one line of code: "wrap this in a cache" and "I am asserting this function is pure." The wrapper - hand-rolled, `@lru_cache`, or `useMemo` - handles the mechanics; the notebook idea from Phase 1 is all that's happening underneath, and you're responsible for the assertion. Phase 3 covers what happens when that assertion turns out to be false, and the other ways this technique backfires even when the function genuinely is pure. --- # When it backfires Memoization trades memory for time - you spend space storing answers so you never spend time recomputing them. That trade is excellent right up until the memory side stops being free, or until the function you cached wasn't safe to cache in the first place. Both failure modes are quiet: nothing crashes or throws an error, things just get slowly worse, or silently wrong. ## Unbounded memory growth The notebook from Phase 1 has to live somewhere, and if nothing ever removes entries from it, it grows for as long as the program runs. A function memoized with no limit, called with a constantly widening range of arguments, builds a cache that never shrinks. ```text day 1: cache has entries for inputs seen so far -> a few thousand day 30: cache still holds every entry from day 1, plus everything since day 90: cache is enormous, most entries haven't been looked up in weeks ``` *What just happened:* nothing here is a bug in the traditional sense - every entry in that cache is a correct, validly computed answer. The problem is that the cache has no concept of "this entry is probably never getting asked for again," so it holds onto all of it, forever, using memory that could otherwise be freed. Left running long enough, this is a slow memory leak with a caching mechanism as the vehicle. This is exactly why real memoization tools bound themselves. `functools.lru_cache(maxsize=128)` keeps at most 128 entries - once it's full, adding a new one evicts the **least recently used** entry to make room. That's what the "LRU" in the name means: it's a cache with an eviction policy built in, precisely so it doesn't grow without limit. ```python @lru_cache(maxsize=128) # bounded - old, unused entries get evicted def expensive(n): ... @lru_cache(maxsize=None) # unbounded - every entry lives forever def risky(n): ... ``` *What just happened:* `maxsize=None` is a legitimate choice when you know the space of possible arguments is small and fixed - Fibonacci of `n` up to, say, 90 has at most 91 possible cache entries, ever. It's a dangerous default when the arguments come from open-ended input, like user IDs or search queries, where the number of distinct inputs can keep growing indefinitely. > A cache with no eviction policy isn't really a cache. It's a growing pile of memory with lookup syntax. ## Memoizing something that isn't actually pure Phase 2 named purity as the hard requirement. Here's what actually happens when that requirement is quietly violated - not a crash, but a wrong answer delivered with total confidence. ```python @lru_cache(maxsize=None) def get_price(product_id): return database.lookup_price(product_id) # reads live data ``` *What just happened at first:* `get_price(42)` runs, hits the database, gets back `19.99`, and caches it. Every subsequent call to `get_price(42)` returns `19.99` from the cache - fast, and correct, for now. *What happens next:* the product's price changes in the database - a sale ends, a price update ships. `get_price(42)` is called again, but it does not go back to the database: it returns `19.99` from the cache, because as far as the memoization wrapper is concerned, `42` is `42` and the cached answer is still sitting right there. The function keeps returning the stale price for as long as the process runs, with no error, no warning, and nothing in the logs to suggest anything is wrong - worse than a crash, because a crash gets noticed and fixed, while a silently stale cached value just ships to customers. The fix isn't a trick - it's recognizing that `get_price` was never actually pure, so it was never a valid memoization candidate. The real options are: don't memoize it, memoize a genuinely pure sub-piece of it if one exists, or reach for something built to handle values that intentionally change over time - which is the next distinction. ## How this differs from general-purpose caching Memoization and "a cache" are related but not the same thing, and conflating them is where a lot of the confusion above comes from. ```text memoization: per-function, per-process, tied to one pure function's arguments, usually lives only as long as that process runs, no built-in concept of "this value expired" general cache (e.g. Redis): shared across processes and machines, explicit time-to-live (TTL) so entries expire on purpose, built for values that are *expected* to change, with explicit invalidation when they do ``` *What just happened:* memoization has no concept of time passing - it assumes the answer for a given input is eternally true, because that's exactly what purity guarantees. A general-purpose cache like Redis is built for the opposite assumption: the underlying data *will* change, so every entry gets a TTL (an expiration time) and the application explicitly invalidates entries when it knows the underlying data changed. `get_price` from the example above belongs in a system like that - a cache with a TTL of a few minutes, or explicit invalidation when a price updates - not in a memoization wrapper that never expires anything. The dividing line: memoization is for computation you want to avoid repeating on unchanging pure math. A shared cache is for data you're willing to serve slightly stale, on purpose, for a bounded window, with a plan for when it goes stale.