Memoization

Overview

Memoization stores the result of a function for a given set of arguments so repeated calls return instantly. It is the top-down flavor of dynamic programming: keep the natural recursive structure but cache overlapping subproblems. This can collapse exponential recursion into linear time at the cost of O(n) extra space for the cache.

Syntax / Usage

Wrap a recursive function with a cache keyed by its arguments. Python's functools.lru_cache does this automatically, or you can pass an explicit dictionary.

from functools import lru_cache

@lru_cache(maxsize=None)              # O(n) time and space after memoization
def fib(n):
    if n < 2:                         # base cases
        return n
    return fib(n - 1) + fib(n - 2)    # each n computed once, then cached

Examples

Without a cache, fib is exponential; memoization makes large inputs instant:

print(fib(50))  # 12586269025 (computed in linear time)

Manual memoization with a dict, useful when arguments are unhashable or you want control:

def climb_stairs(n, memo=None):       # ways to climb n stairs 1 or 2 at a time
    if memo is None:
        memo = {}
    if n <= 2:
        return n
    if n not in memo:
        memo[n] = climb_stairs(n - 1, memo) + climb_stairs(n - 2, memo)
    return memo[n]

print(climb_stairs(10))  # 89

Common Mistakes

• Using a mutable default argument like memo={} at the top level, which is shared across calls.
• Caching on unhashable arguments (lists, dicts) without converting them to tuples first.
• Applying lru_cache to functions with side effects, hiding bugs behind cached returns.
• Letting an unbounded cache grow forever in long-running processes; set a maxsize.
• Memoizing problems without overlapping subproblems, where the cache adds overhead for no gain.

See Also

algorithms-dynamic-programming algorithms-recursion algorithms-big-o-notation