Basic

Remembering past answers

Some recursions ask the same question many times. Storing each answer the first time, then reusing it, turns repeated work into a lookup.

What you will see

About 3 min of reading

Try It

Cache a slow recursion.

Fib 10 slow.

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

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Fib 30 cached.

memo = {} def fib(n): if n < 2: return n if n in memo: return memo[n] memo[n] = fib(n - 1) + fib(n - 2) return memo[n] print(fib(30))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

832040

Fib 40 with lru_cache.

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(40))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

102334155

Ways to climb 8.

memo = {} def ways(n): if n <= 1: return 1 if n not in memo: memo[n] = ways(n - 1) + ways(n - 2) return memo[n] print(ways(8))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Put it in order

Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.

Data Flow

Recursions with overlapping subproblems repeat work. Caching each answer by its argument turns those repeats into fast lookups.

1 same call repeats

↓

2 store answer by argument

↓

3 later call reads cache

↓

4 work becomes linear

Line by line

Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.

def fib(n): sets nothing on screen

if n < 2: sets nothing on screen

return n sets nothing on screen

return fib(n - 1) + fib(n - 2) sets nothing on screen

print(fib(10)) 55

Why this works

Only cache repeats

Memoization pays off when the same argument is computed many times. If each argument is used once, a cache only wastes memory.

Pure calls only

A cached call must give the same answer for the same argument. If it reads changing state, the cache is wrong.

Examples

Slow fib

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

fib(10) recomputes fib(5) over and over. The same call appears in many branches.

Cache with a dict

memo = {}
def fib(n):
    if n < 2:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]
print(fib(30))

Store the answer the first time. Later calls read it from the dict instead of recomputing.

lru_cache

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(40))

The decorator caches by argument. One line turns the slow recursion into a fast one.

Each n once

memo = {}
def f(n):
    if n < 2:
        return n
    if n not in memo:
        memo[n] = f(n - 1) + f(n - 2)
    return memo[n]
print(f(12))

With a cache each distinct n is computed once. The count of calls becomes linear.

Memo needs a key

memo = {}
def ways(n):
    if n <= 1:
        return 1
    if n not in memo:
        memo[n] = ways(n - 1) + ways(n - 2)
    return memo[n]
print(ways(8))

The cache key is the argument. Only pure calls with a stable key can be cached.

Cache saves time not depth

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(20))

The cache removes repeated work but the calls still nest. Depth is unchanged.

Repeated subproblems

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

fib(4) appears in both branches of fib(6). Overlapping subproblems are what caching fixes.

Cache grows with n

memo = {}
def f(n):
    if n < 2:
        return n
    if n not in memo:
        memo[n] = f(n - 1) + f(n - 2)
    return memo[n]
print(len(memo))

The cache holds one entry per distinct argument. Memory trades for speed.

Words this lesson uses

Each one is defined here on this site. Open the entry for the full definition and the other words it points at.

← Recursion on nested data

Previous Lesson

Recursion on nested data

Next Lesson

Divide and conquer

Divide and conquer →