Memoisation

Memoisation is the shortest way from a recursive rule to a DP: keep the recursion exactly as it is, and store each answer the first time it is worked out. This lesson covers how to do it in Python, the order in which answers appear, when it beats a table, and the limit that stops it on large inputs.

Remember each answer

RECR-3 met memoisation with Fibonacci. The pattern is the same for any DP. The memo is a dictionary from a state to its answer. Before working out a state, look it up; after working it out, store it.

def fewest_coins(amount, coins):
    memo = {0: 0}                  # the base case

    def f(x):
        if x not in memo:
            memo[x] = 1 + min(f(x - c)
                              for c in coins if c <= x)
        return memo[x]

    return f(amount)

Each state is worked out once. Every later request for it is a lookup in the dictionary, which takes O(1) time on average (HASH). So the cost is the DP cost from lesson 1: the number of states times the work per state.

When a state has more than one number, the key is a tuple: memo[(r, c)]. A tuple can be a dictionary key because it cannot change; a list cannot.

functools.cache

Python can add the memo for you. The decorator @cache wraps a function and keeps a dictionary from its arguments to its result.

from functools import cache

def grid_paths(rows, cols):
    @cache
    def paths(r, c):
        if r == 0 or c == 0:
            return 1
        return paths(r - 1, c) + paths(r, c - 1)

    return paths(rows - 1, cols - 1)

• @lru_cache(maxsize=None) does the same as @cache. With a number for maxsize it keeps only that many recent answers (HASH-7), which is rarely what a DP wants.
• Every argument must be hashable (HASH-1): numbers, strings and tuples are; lists, sets and dicts are not. Pass tuple(a), or better, pass only the numbers that change (positions) and read the list from outside the function.
• paths.cache_info() reports hits (lookups that found an answer), misses (states worked out) and the size. paths.cache_clear() empties it.

The order answers arrive

Memoised recursion does not fill the table in a neat order. It fills a state when its call finishes, and a call finishes only after all the calls it makes. Step through the figure, which counts paths to the cell (2, 3) of a small grid.

Three things to see. The answers arrive deep cells first, in the order the calls return. A cell that no call needs, here (0, 0), is never filled. And while the first answers are being found, a whole chain of calls is waiting: 5 calls for this grid, about r + c for the cell (r, c).

Only the states you reach

The second point can matter a great deal. Take f(0) = 1 and f(n) = f(n // 2) + f(n // 3), where // divides and rounds down. For n = 10¹⁸ (a 1 followed by 18 zeros), a table from 0 to n is impossible. But starting from n, the recursion only ever reaches numbers of the form n divided by some 2s and some 3s, rounded down.

from functools import cache

@cache
def f(n):
    return 1 if n == 0 else f(n // 2) + f(n // 3)

f(10 ** 18)          # 224412958156019
f.cache_info()       # ... currsize=1012

Only 1,012 different states are ever reached, and the calls go at most about 60 deep (each call at least halves n). When the states a problem really needs are few and scattered among a huge range, memoisation is the right tool, and a table is the wrong one.

The recursion limit

Each waiting call keeps a frame in memory (RECR-2), and Python stops at about 1,000 nested calls with a RecursionError. sys.getrecursionlimit() shows the limit. A memoised f(x) for the coins calls f(x − 1), which calls f(x − 2), and so on, so an amount of 100,000 needs 100,000 nested calls. The grid in the figure needs about r + c.

• sys.setrecursionlimit(200_000) raises the limit. It is risky: each frame takes memory, and in some places, including the Python that runs these practice pages in the browser, a very deep recursion can crash the whole program instead of raising an error.
• In the browser, @cache makes this worse. The cache wrapper is written in C, and each cached call also uses the browser’s own, smaller stack, so a cached function can stop after only about 250 nested calls. A memo kept in a dictionary, as in fewest_memo.py, goes further.
• A loop that asks for small states first keeps the depth low. It fills the memo 500 states at a time, so no call goes more than about 500 deep. It works, but it is a sign that a table is the better tool.

  for x in range(0, n, 500):
      f(x)                 # fills f(0) to f(x)
  f(n)
  

• The real fix is to fill the table with a loop: tabulation, the next lesson. It has no depth limit and is also faster, because a function call and a dictionary lookup cost more than reading a list. For the grid above, the loop version is about 7 times faster.

Now try DYNP-P2, Exchanging a coin, where only a memo will do.