Memoising Subproblems That Never Repeat

A memo on merge sort stores every call and finds none of them again.

Memoisation saves time only when the same subproblem is asked for more than once, and on a recursion whose subproblems never repeat it costs memory and saves nothing. This card memoises merge sort, a divide-and-conquer algorithm, beside Fibonacci, a dynamic programme, and counts how often each memo is used.

The symptom is a recursion that is no faster with a memo and uses far more memory. The trigger is memoising by reflex, because a recursive function looked like a dynamic programme. The listing below keys a memo by each call's range of the array, (lo, hi), and counts the hits: the calls answered from the memo instead of computed.

memo_no_repeats.pypy

def merge_sort_memoised(values: list[int]) -> tuple[list[int], int, int, int]:
    memo: dict[tuple[int, int], list[int]] = {}
    hits = 0

    def sort(lo: int, hi: int) -> list[int]:
        nonlocal hits
        if (lo, hi) in memo:
            hits += 1
            return memo[(lo, hi)]
        if hi - lo <= 1:
            result = values[lo:hi]
        else:
            mid = (lo + hi) // 2
            left, right = sort(lo, mid), sort(mid, hi)
            result = []
            i = j = 0
            while i < len(left) and j < len(right):
                if left[i] <= right[j]:
                    result.append(left[i])
                    i += 1
                else:
                    result.append(right[j])
                    j += 1
            result += left[i:] + right[j:]
        memo[(lo, hi)] = result
        return result

    return sort(0, len(values)), hits, len(memo), sum(map(len, memo.values()))


def fibonacci_memoised(n: int) -> tuple[int, int, int]:
    memo: dict[int, int] = {}
    hits = 0

    def fib(k: int) -> int:
        nonlocal hits
        if k in memo:
            hits += 1
            return memo[k]
        result = k if k < 2 else fib(k - 1) + fib(k - 2)
        memo[k] = result
        return result

    return fib(n), hits, len(memo)


values = [(i * 7919) % 1024 for i in range(1024)]
ordered, hits, stored, kept = merge_sort_memoised(values)
assert ordered == sorted(values)
print(f"merge sort, 1024 items: {stored} entries stored, holding {kept} values, {hits} hits")
value, hits, stored = fibonacci_memoised(30)
print(f"fibonacci(30) = {value}: {stored} entries stored, {hits} hits")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

merge sort, 1024 items: 2047 entries stored, holding 11264 values, 0 hits
fibonacci(30) = 832040: 31 entries stored, 28 hits

The mechanism is in the ranges. Merge sort splits each range into two halves that never meet again, so every (lo, hi) pair is asked for exactly once: 2,047 calls, 2,047 entries and 0 hits. Fibonacci asks for fib(28) from both fib(30) and fib(29), and the same for every smaller value, so 31 entries answered 28 calls that would otherwise have been recomputed.

The cost is memory. Each merge sort entry holds a sorted list, and the memo held 11,264 values for a 1,024-item input: 1,024 at each of the 11 levels of the recursion, where plain merge sort needs room for about 1,024 at a time. A larger input or a memo kept across calls grows the waste with it.

The remedy is to check that subproblems overlap before adding a memo. Draw two levels of the call tree, or count the hits on a small input as the listing does: zero hits means divide and conquer, and the memo should go.

On the Algorithms: Design Strategies cheatsheet

← → move through sections and cards