Memoization from First Principles: Building and Tracing a Cache

The Problem Memoization Solves

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

For fib(5), count the calls:

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1) = 1
│   │   │   └── fib(0) = 0
│   │   └── fib(1) = 1
│   └── fib(2)
│       ├── fib(1) = 1
│       └── fib(0) = 0
└── fib(3)
    ├── fib(2)
    │   ├── fib(1) = 1
    │   └── fib(0) = 0
    └── fib(1) = 1

• fib(2) is computed 3 times.
• fib(1) is computed 5 times.
• fib(0) is computed 3 times.

For fib(50) this becomes catastrophically slow. Memoization solves this by caching results and returning them immediately on repeated calls.

Manual Implementation

def memoized_fib(n, cache={}):
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    cache[n] = memoized_fib(n - 1, cache) + memoized_fib(n - 2, cache)
    return cache[n]

Trace the cache state during memoized_fib(5):

The cache hits on fib(2) and fib(3) eliminate the redundant subtree computations entirely.

Building a General Memoize Decorator

def memoize(func):
    cache = {}
    def wrapper(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrapper

@memoize
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(10))
print(fibonacci.__closure__[0].cell_contents)

Output:

55
{(1,): 1, (0,): 0, (2,): 1, (3,): 2, (4,): 3, (5,): 5, (6,): 8, (7,): 13, (8,): 21, (9,): 34, (10,): 55}

The cache is a dictionary inside the closure. Keys are argument tuples. Each unique input is computed exactly once.

functools.lru_cache

from functools import lru_cache

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

print(fibonacci(10))
print(fibonacci.cache_info())

Output:

55
CacheInfo(hits=8, misses=11, maxsize=128, currsize=11)

lru_cache uses a Least Recently Used eviction policy when the cache reaches maxsize. The cache_info() method shows how many hits and misses occurred.

The space-time trade-off in memoization is worth understanding deeply for interview discussions: you are trading memory for computation time. For problems with exponential time complexity and polynomial unique subproblems, memoization converts an intractable problem to a tractable one.

Practice memoization tracing problems at pycodeit.com.