DEV Community

Cover image for Memoization from First Principles: Building and Tracing a Cache
Ameer Abdullah
Ameer Abdullah

Posted on

Memoization from First Principles: Building and Tracing a Cache

#programming #python #productivity #beginners

Understanding memoization by implementing it manually and watching the cache state change alongside each recursive call.

Memoization is one of those concepts that is trivial to use with functools.lru_cache and poorly understood when asked to implement manually. Building it from scratch and tracing the cache state alongside the call stack produces genuine understanding.

The Problem Memoization Solves 

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

Trace the cache state during memoized_fib(5):

Call Cache before Returns Cache after
fib(5) {} (computing)
fib(4) {} (computing)
fib(3) {} (computing)
fib(2) {} (computing)
fib(1) {} 1 {}
fib(0) {} 0 {}
fib(2) resolves {} 1 {2: 1}
fib(1) {2:1} 1 {2: 1}
fib(3) resolves {2:1} 2 {2:1, 3:2}
fib(2) {2:1, 3:2} 1 (cache hit) {2:1, 3:2}
fib(4) resolves {2:1, 3:2} 3 {2:1, 3:2, 4:3}
fib(3) {2:1, 3:2, 4:3} 2 (cache hit) {2:1, 3:2, 4:3}
fib(5) resolves {2:1, 3:2, 4:3} 5 {2:1, 3:2, 4:3, 5: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)
Enter fullscreen mode Exit fullscreen mode

Output:

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

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())
Enter fullscreen mode Exit fullscreen mode

Output:

55
CacheInfo(hits=8, misses=11, maxsize=128, currsize=11)
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)