Skip to content
BENIBIX Learn

Memoization

Development🧮 Algorithms & Data StructuresAlgorithm Design Techniques

Also known as Memoize, Memoisation, functools.cache

Saving a function's answer for each input. The same call is then instant.

Think of it like

Think of it like a note on the fridge. It holds an answer you already worked out.

Example

Lucy adds @functools.cache to her Fibonacci function. fib(50) comes back at once instead of running for hours.

Why it matters

One line can turn a function that never finishes into one that answers at once.

Definition

Memoization means saving what a function gives back for each input. The next call with that input is then instant. The saved answers sit in a table, often a hash table keyed by the input. It is only safe on pure functions, whose answer never changes for the same input. In Python, one line with functools.cache adds it. It is the top-down way to do dynamic programming.

Example code

python
import functools

@functools.cache
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print(fib(50))  # 12586269025
Each fib(n) is worked out once, then read from the cache.

Common mistake

Memoizing a function that reads the clock or a database. It keeps giving back an old, wrong answer.

Key takeaways

  1. 1
    Save each answer. Keyed by its input.
  2. 2
    Pure functions only. Same input, same answer.
  3. 3
    Top-down DP. One kind of dynamic programming.