Memoization Techniques — Core Concepts

What memoization solves

Memoization is an optimization technique that stores the results of expensive function calls and returns the cached result when the same inputs occur again. It works when a function is pure — same inputs always produce the same output, with no side effects.

The classic example: Fibonacci without memoization calls itself about 2ⁿ times. With memoization, it calls itself exactly n times. The difference between O(2ⁿ) and O(n) is the difference between “heat death of the universe” and “instant.”

Python’s built-in memoization

@lru_cache

Python’s functools.lru_cache is the easiest way to memoize any function:

from functools import lru_cache

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

fibonacci(100)  # instant — computes 100 values, not 2¹⁰⁰

maxsize=None means unlimited cache. With a number like maxsize=128, it keeps only the 128 most recently used results — an LRU (Least Recently Used) eviction policy.

@cache (Python 3.9+)

A shorthand for @lru_cache(maxsize=None):

from functools import cache

@cache
def expensive_computation(x, y):
    # ... complex math ...
    return result

Cache statistics

fibonacci(50)
print(fibonacci.cache_info())
# CacheInfo(hits=48, misses=51, maxsize=None, currsize=51)

The hits count tells you how many redundant calls were avoided. High hit rate means memoization is working well.

When memoization works

Three conditions must be met:

1. Same inputs → same output (pure function). Functions that read files, make network calls, or depend on global state are not suitable unless you handle invalidation.

2. The function is called repeatedly with the same arguments. If every call has unique arguments, memoization just wastes memory storing results that are never reused.

3. Arguments are hashable. Python’s cache uses a dictionary internally, so arguments must be usable as dictionary keys. Strings, numbers, and tuples work. Lists and dicts do not.

Manual memoization

Sometimes @lru_cache does not fit — your arguments are not hashable, or you need custom eviction logic:

def grid_paths(m, n):
    memo = {}

    def helper(r, c):
        if (r, c) in memo:
            return memo[(r, c)]
        if r == 0 or c == 0:
            return 1
        result = helper(r - 1, c) + helper(r, c - 1)
        memo[(r, c)] = result
        return result

    return helper(m - 1, n - 1)

This pattern — check cache, compute if missing, store and return — is the essence of memoization regardless of which tool you use.

Memoizing with unhashable arguments

When arguments include lists, convert to tuples for caching:

@lru_cache(maxsize=None)
def solve(items_tuple, capacity):
    items = list(items_tuple)
    # ... solve knapsack ...

# Call with tuple conversion
solve(tuple(items), capacity)

Memoization vs caching

These terms are related but not identical:

• Memoization is a specific optimization for function calls — store results keyed by arguments.
• Caching is broader — storing any computed result for reuse, including database query results, API responses, and rendered HTML.

Memoization is always about pure functions. Caching often involves impure operations where you must handle invalidation (“when does the cached value become stale?”).

Common misconception

“Memoization makes everything faster.” It only helps when there are overlapping subproblems — the same function being called with the same arguments multiple times. For a function that is called once per unique input (like processing each line of a file), memoization adds overhead without benefit. The cache lookup costs time and memory with zero hits.

Space-time tradeoff

Memoization trades memory for speed. For Fibonacci(1000), the cache stores 1,000 entries — trivial. But for a function with two arguments each ranging from 0 to 10,000, the cache could store up to 100 million entries. Monitor memory usage:

import sys

@lru_cache(maxsize=None)
def big_computation(x, y):
    return x ** y % 1000000007

# After many calls:
info = big_computation.cache_info()
print(f"Cache size: {info.currsize} entries")

Use maxsize to cap memory when the full cache would be too large. The LRU policy ensures frequently-used results stay cached while rare ones are evicted.

One thing to remember: Memoization is the easiest performance optimization in Python — add @cache to a pure function with repeated calls and watch it fly. But only use it when the function is actually called with the same arguments multiple times.