Memoization Mechanics: Cache Keys, Laziness, and Recursion Depth

A memoized function is a function with a side table. The body stays a plain recursive definition; a wrapper checks the table before computing and stores the result after. It is the lazy evaluation order of the recurrence described in recurrences as DAGs, where the cache plays the role of the visited set. The correctness requirement is that the function be pure with respect to the key: for a given key, the returned value must depend on nothing else, and the function must not change observable state. When that holds, replacing a repeated call with a lookup is a valid optimization; when it does not, memoization silently returns stale answers, and the bug is usually far from the cache.

The standard formulation of the technique predates the name by a decade. Bellman’s 1957 monograph describes the same table-filling idea from the side of the recurrence; memoization as a programming technique is usually attributed to a 1968 note by Michie on “memo functions” in machine learning programs, which proposed caching computed values of a function to avoid recomputation.

What the wrapper must key on

The cache key must include every parameter that influences the result. Three failure patterns account for most incorrect memoization.

Implicit parameters. A recursive helper that closes over a mutable variable — an index pointer, an accumulator, a global “current best” — has state that does not appear in its argument list. Two calls with identical arguments can then return different values, and the cache is wrong by construction. The repair is either to pass the implicit state explicitly, so it becomes part of the key, or to prove the implicit state is constant for the lifetime of the memo.

Object identity versus value. Caching by reference on a mutable structure is unsound because the structure can change after the entry is written. Caching by value requires hashing the whole structure, which for a list or array of length n costs O(n) per lookup and erases the asymptotic gain. For subarray problems the usual repair is to key on index bounds (lo, hi) into an immutable input, which is O(1) to hash and unambiguous as long as the input is not mutated during the computation.

Floating-point and non-hashable keys. Keys containing floats are hashable but equality on them is exact, so 0.1 + 0.2 and 0.3 land in different buckets. Keys containing lists or dicts are unhashable in Python and must be converted to tuples, which costs a copy at every call.

In C++ the same problem is expressed in the type system: std::unordered_map<std::vector<int>, long long> is legal — std::hash is specialised for std::vector — but it hashes the entire vector on every lookup, and std::map requires a strict weak ordering over vectors that costs a lexicographic comparison. Encoding the state as a single integer — ((i * W) + j) for a table of width W — collapses the key to one machine word and is the usual choice when the state dimensions are bounded.

The cache also has to represent “absent”

A cache stores values, but the caller also needs to distinguish “not computed” from “computed and the answer is zero” or “computed and there is no answer”. In Python, functools.lru_cache distinguishes a cache miss from a cached None internally, so returning None to mean “infeasible” is safe: the None is stored as a value and returned on a hit rather than being mistaken for an absent entry. In languages where the cache is a plain dictionary or array, the sentinel matters: an int table initialized to -1 cannot hold a legitimate answer of -1, and a table initialized to 0 cannot distinguish an uncomputed cell from a genuine zero. Use a separate boolean array, an explicit optional type, or a value outside the answer’s range.

The same issue appears in the recursion itself. A memoized search that returns -1 for “impossible” and is cached on that basis must not also use -1 as the initial sentinel, because the first probe of an infeasible state would look like a hit and the second would recurse forever.

from functools import cache

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

# Equivalent memoized form; `cache` is the unbounded variant of lru_cache.
@cache
def fib_memo(n):
    if n < 2:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

cache was added to functools in Python 3.9 as a thin wrapper over lru_cache(maxsize=None). The distinction between the two is memory policy, not semantics: lru_cache with a finite maxsize evicts entries and therefore can recompute a state that is requested again after eviction. That makes the asymptotic bound dependent on access pattern, which is exactly the property an unbounded table avoids.

Laziness is the reason to prefer top-down

Bottom-up tabulation evaluates every state in the table, whether or not the answer depends on it. Top-down memoization evaluates only states reachable from the initial call. For the subset-sum recurrence over (index, remaining) with n items and capacity C, the table has n·C cells; a particular instance may reach only a small fraction of them, in which case the memoized version does strictly less work.

The advantage reverses when the reachable set is dense. Then the memoized version pays overhead the table does not: a hash lookup per call, a function call frame per state, and the memory cost of the dictionary, which for a Python dict is substantially larger per entry than an array slot. A dict holding k entries needs more memory than an array of k integers by a factor that grows with the size of the key and the per-entry bookkeeping. When the reachable set is most of the table, the memoized version is the same computation with a heavier constant.

The structural advantage of the top-down form is different and more interesting: it lets the programmer write the recurrence exactly as stated, without deriving a topological order. For recurrences whose dependency direction is awkward — for example, where the state after a transition depends on a quantity computed later in the input — the bottom-up order can be difficult to find while the recursive definition is immediate. Top-down pays for that convenience with call depth.

Recursion depth is a hard limit, not a slowdown

Every memoized state that is computed by recursing into another state adds a stack frame. If the state graph has a path of length L, the memoized version needs L frames. Python’s default recursion limit is 1000 frames, and exceeding it raises RecursionError; the limit counts Python frames, and a memoized function typically uses one frame per state transition plus whatever the wrapper adds. A DP over a string of length 5000 with a state per character therefore fails, not because the algorithm is wrong but because the host cannot represent the stack.

Three repairs exist, in increasing order of intrusiveness. Raise the interpreter’s limit and the thread’s stack size together — raising one without the other converts a clean RecursionError into a segmentation fault, since the limit is a check in the interpreter while the stack is a fixed allocation from the OS. Convert to an explicit stack, pushing state tuples onto a list and popping them, which makes the depth a heap allocation. Or derive a bottom-up order, which needs no stack at all. The third is usually the right answer when the dependency structure permits it.

def min_coins_memo(coins, target):
    from functools import cache
    INF = float('inf')

    @cache
    def best(s):
        if s == 0:
            return 0
        if s < 0:
            return INF
        return min((1 + best(s - c) for c in coins), default=INF)

    ans = best(target)
    return -1 if ans == INF else ans

The depth here is at most target / min(coins), so a target of 10^5 with a smallest coin of 1 needs 10^5 frames and fails on a default-configured CPython. The bottom-up version of the same recurrence, shown in the state-graph article, uses constant stack and a single array.

Mutating the cache while iterating

A subtler failure: a memoized function whose body inspects the cache, or whose recursion is interleaved with writes from another thread. Two threads calling the same memoized function concurrently can both miss, both compute, and both insert; the results are equal if the function is pure, so the duplicate work is wasted but the answer is correct. In Python, lru_cache holds a lock during the cache bookkeeping, but the lock is released while the wrapped function runs, so duplicate computation is possible and the wrapped function is called more than once for the same key. The guarantee is therefore “at most one cached entry per key”, not “at most one call per key”.

Recursive memoization inside a single thread has a related hazard: re-entering the same state before its entry is written. For a well-founded recurrence that cannot happen, because the recursion strictly descends; this is the acyclicity condition from recurrences as DAGs. For a recurrence with a cycle — a game graph with draws, a shortest-path problem with negative weights — the memoized function will recurse indefinitely unless the cycle is detected explicitly with an in-progress marker. Detecting it means the state is not a simple function of smaller states, and the correct treatment is usually a fixed-point iteration rather than memoization.

Choosing between the two forms

The decision reduces to three questions. Is the reachable state set a small fraction of the full table? If so, memoize. Is the maximum dependency chain longer than the available stack? If so, tabulate. Is the transition structure such that a topological order is hard to state but easy to compute recursively? If so, memoize and accept the depth.

There is a fourth consideration that is easy to overlook: the memoized version can be reused across queries on the same input, since the cache persists between calls. A tabulated version usually allocates a fresh table per query. For a program answering many queries over one fixed input — the usual shape of a dynamic-programming solution embedded in a larger service — a persistent memo can amortize the whole computation across queries, at the cost of retaining memory proportional to the reachable state set for the process lifetime.