Memoization

Memoization caches the results of function calls so repeated calls with the same arguments return instantly instead of recomputing.

Cache what you compute

Memoization is a technique for speeding up functions by storing the result of each distinct call and returning the stored value when the same arguments recur. It turns a recursion that recomputes overlapping subproblems into one that computes each subproblem only once. It is the top-down face of dynamic programming.

From exponential to linear

The naive recursive Fibonacci makes two calls per level and recomputes the same values exponentially many times, costing O(2^n). Adding a cache keyed by n means each Fibonacci value is computed once and read thereafter, collapsing the cost to O(n). The transformation requires no change to the recurrence, only a lookup at the top of the function.

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

• Works when calls are pure: same input always gives same output
• Cache key is the tuple of arguments
• Trades memory for time
• Automatic in many languages via a decorator or wrapper

Requirements and limits

Memoization only works for pure functions whose output depends solely on their arguments, with no side effects or hidden state. The cache consumes memory proportional to the number of distinct calls, so an unbounded cache can grow large; bounded caches such as least-recently-used discard old entries to cap memory at the cost of occasional recomputation.

Memoization versus tabulation

Memoization computes subproblems lazily, only those actually reached, which can save work when the reachable set is sparse. Bottom-up tabulation computes every subproblem eagerly but avoids recursion overhead and can often reduce space by keeping only the recent rows of the table. The two are complementary faces of the same dynamic-programming idea.