AI Hints
Home›DSA in Python Tutorial›Recursion Practice
DSA in Python · Lesson 44 of 132

Memoization

Remember answers.

⏱ 2 min read▶ Video at 50:57🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Memoization
From the video: Memoization
  • 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.

fib_slow.pypython
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")
Output
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.

fib_fast.pypython
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))
Output
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
Next up: Practice: Flatten a List — lists inside lists