Time–space trade-offs with memoization
Many algorithms can trade memory for speed. Memoization stores the result of a function for each distinct argument so a repeated call returns the stored answer instead of recomputing it. It helps when a recursive solution solves the same subproblems again and again.
Python
calls = 0
def fib_slow(n):
global calls
calls += 1
return n if n < 2 else fib_slow(n - 1) + fib_slow(n - 2)
def fib_memo(n, cache):
global calls
calls += 1
if n in cache:
return cache[n]
cache[n] = n if n < 2 else fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
return cache[n]
calls = 0
slow = fib_slow(20)
slow_calls = calls
calls = 0
fast = fib_memo(20, {})
fast_calls = calls
print(slow, slow_calls)
print(fast, fast_calls)
assert slow == fast