Memoization

The Idea

Memoization stores each subproblem's answer the first time you compute it. Every later call with the same input reads the stored value instead of recursing again. The shape of the code barely changes, but the cost collapses from exponential to linear.

Real-World Example

A translator working through a technical manual keeps a glossary card for every term they look up. The second time "torque converter" appears, they read their own card instead of opening the dictionary from scratch.

The Code

def fib(n, memo=None):
    if memo is None:
        memo = {}
    if n < 2:
        return n
    if n in memo:                              # solved before: reuse it
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

print(fib(35))   # 9227465, in 69 calls instead of nearly 30 million

calls = 0
memo = {}

def f(n):
  global calls
  calls += 1
  if n < 2:
      return n
  if n not in memo:
      memo[n] = f(n - 1) + f(n - 2)
  return memo[n]

f(5)
print(calls)