Memoization
Remember answers.
Some recursive functions solve the same small problems again and again, millions of times. Memoization means remembering each answer the first time you work it out, so you never work it out twice.

- The same problems, again and again
- Remember each answer
- Never work it out twice
Slow Fibonacci
Each Fibonacci number is the sum of the two before it. The simple recursive version calls itself twice, and those calls call themselves twice, and so on. We count the calls. Run it. Fibonacci of thirty needs over a million calls, because the same values are recalculated over and over. That's exponential time.
calls = 0
def fib(n):
global calls
calls += 1
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(30), "after", f"{calls:,}", "calls")832040 after 2,692,537 calls
Fast Fibonacci
Now we add one line. LRU cache, from the functools module, remembers every answer the function returns. The second time fib of twenty is needed, it's returned instantly. Run it. Just thirty one calls for fib of thirty, and fib of three hundred is instant too.
from functools import lru_cache
calls = 0
@lru_cache(maxsize=None)
def fib(n):
global calls
calls += 1
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(30), "after", calls, "calls")
print(fib(300))832040 after 31 calls 222232244629420445529739893461909967206666939096499764990979600
Summary
Memoization stores answers, so each one is worked out once. LRU cache adds it in one line. This idea is the heart of dynamic programming, later in the course.
Key takeaways- Remember answers
- @lru_cache
- Exponential → linear