This lesson's interactive features are locked, please to keep using them

Memoization

Memoization is an optimization technique used primarily to speed up programs by storing the results of expensive function calls and using cached results when the same inputs occur repeatedly.

Memoization vs. Caching

Memoization is a specific type of caching. While caching can refer generally to any storing technique, for example web page caching, memoizing specifically involves caching the return values of a function for algorithmic use.

Tradeoffs

Adding memoization is a way to lower a function's time cost in exchange for space cost. In most cases, this means trading memory (RAM) for compute resources (CPU). Memoized functions become optimized for speed in exchange for a higher use of memory space.

Memoized Fibonacci

def fibonacci(n: int, memo: dict[int, int] | None = None) -> int:
    if memo is None:
        memo = {}
    if n not in memo:
        if n == 0:
            memo[n] = 0
        elif n == 1:
            memo[n] = 1
        else:
            memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]