Hack University
Course outline · 0% complete

0/30 lessons0%

Course overview →

Memoization: remember what you solved

lesson 5-3 · ~13 min · 15/30

Memoization

Lesson 5-2 ended with the diagnosis. Naive fib is exponential because it re-solves the same subproblems, and the cure is embarrassingly simple.

Keep a dictionary. Before computing, check it. After computing, store the answer in it.

That dictionary is called a memo, which is where memoization gets its name, and it changes the math completely.

Each distinct argument is computed once, and every repeat is an O(1) dictionary hit. For fib that means O(n) total instead of O(2ⁿ).

The recipe for memoizing any recursive function is three lines.

  1. if n in memo: return memo[n] at the top.
  2. Compute as usual.
  3. memo[n] = result before returning.

The requirement to watch is that the function must be pure, meaning its answer depends only on its arguments. Caching a function whose result depends on the time or on a database read returns stale answers instead of fast ones.

fib with a memo

The same function, plus a dictionary.

calls = 0

def fib_memo(n, memo):
    global calls
    calls += 1
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

calls = 0
print(fib_memo(20, {}), calls)
calls = 0
print(fib_memo(50, {}), calls)

Output

6765 39
12586269025 99

Compare with lesson 5-2. fib(20) drops from 21,891 calls to 39, and fib(50), which would take years naively, finishes instantly in 99 calls.

The call counts are almost exactly 2n − 1, which is the signature of a linear algorithm. Each of the n distinct arguments does real work once, and each also gets hit once from the memo.

The memo check comes before the base case, and either order works here since the base cases are already O(1). What matters is that both come before any recursive call.

The memo is passed down as an argument, so every call in the whole tree shares one dictionary. A fresh {} per call would cache nothing.

Each top-level call gets its own {} here, which is why the counts are comparable. Reusing one memo across both calls would make the second nearly free.

The memo eliminated every call whose answer was already computed, collapsing the repeated subtrees into O(1) dictionary lookups.

Look at the lesson 5-2 figure. The second fib(2) subtree is no longer re-expanded, it returns from the memo immediately, and the entire subtree beneath it never happens.

That is the crucial detail. The saving is not one skipped call, it is one skipped subtree, and skipping a subtree near the top of the tree removes exponentially many calls.

What remains is n distinct arguments, each doing real work exactly once, plus a cheap lookup for each repeat.

The cost model to carry forward is a product: the number of distinct subproblems times the work per subproblem. Here that is n × O(1) = O(n).

That formula is dynamic programming, which unit 9 builds on directly. The only thing that changes there is the order the subproblems get filled in.

trib

Tribonacci, where each value is the sum of the previous three.

def trib(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n == 0:
        return 0
    if n <= 2:
        return 1
    memo[n] = trib(n - 1, memo) + trib(n - 2, memo) + trib(n - 3, memo)
    return memo[n]

print(trib(4))
print(trib(25))

Output

4
1389537

The sequence starts trib(0) = 0, trib(1) = 1, trib(2) = 1, so two base-case checks are needed rather than one.

Every recursive call receives the same memo, written trib(n - 1, memo) and never trib(n - 1). Dropping the argument would restart with an empty dictionary and put the exponential cost straight back.

memo=None with if memo is None: memo = {} is the right way to give it a default. Writing memo={} in the signature would share one dictionary across every top-level call, since Python evaluates default arguments once at definition time.

Checking the arithmetic: trib(3) = 1 + 1 + 0 = 2, and trib(4) = 2 + 1 + 1 = 4.

Three self-calls means the naive tree branches by 3 per level, so it grows like 3ⁿ. trib(25) would be hundreds of millions of calls without the memo and is about 25 with it.

lru_cache: memoization as one line

Memoizing by hand teaches the mechanism, and in production Python you will usually reach for functools.lru_cache from the standard library instead.

It is a decorator, a line starting with @ placed above a function that wraps the function with extra behavior. Here the behavior is exactly the memo: check a cache before computing, store the result after, keyed by the arguments.

You also get a free cache_info() report, which is genuinely useful for confirming the cache is being hit rather than just being present.

Two cautions come up in both interviews and code review.

Arguments must be hashable, so numbers, strings, and tuples work but lists do not, because the arguments become dictionary keys under the hood. Passing a list means converting it to a tuple first.

The cache also lives as long as the function does. maxsize=None means unbounded, and long-running services usually set a bound so memory cannot grow forever, at which point the least-recently-used policy evicts the stalest entries first.

One decorator line

lru_cache does the memoization, and cache_info proves it.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(80))
print(fib.cache_info())

Output

23416728348467685
CacheInfo(hits=78, misses=81, maxsize=None, currsize=81)

The function body has no caching code at all. It is the naive recursion from lesson 5-2, and the decorator supplies everything else.

The report says 81 distinct computations, the misses, and 78 cache hits. Without the cache, fib(80) would take on the order of 2⁸⁰ calls, which is a number with 24 digits.

currsize=81 is the memo's contents, one entry per distinct argument from 0 to 80. That is the O(n) space memoization trades for its time saving.

hits being roughly equal to misses is the linear pattern again. Each argument is computed once and reused about once.

The catch worth knowing is that the cache is attached to the function object, so it persists between calls for the life of the program. fib.cache_clear() resets it when that is not what you want.

The total running time is O(n).

Memoization means each distinct subproblem is solved once, and every repeat costs O(1) as a dictionary lookup.

So the running time is the number of distinct subproblems times the work each does, which is n × O(1) = O(n).

The space is O(n) as well, from the memo holding one entry per subproblem, plus whatever stack depth the recursion reaches.

Carry that formula into unit 9, because dynamic programming is this exact idea organized differently. The interesting cases there are the ones where the work per subproblem is not O(1), such as n subproblems each scanning O(n) options for O(n²) overall.