Caching Recursive Calculations with Memoization
In this lesson, you will learn how to supercharge your recursive functions by automatically storing their results using functools.lru_cache.
The Problem: Redundant Work
Recursive functions often solve the same sub-problems multiple times. Consider a classic recursive Fibonacci function:
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
To calculate fib(5), the program calculates fib(3) multiple times, fib(2) even more, and so on. As n grows, the number of redundant operations explodes exponentially. This is where memoization—storing the results of expensive function calls and returning the cached result when the same inputs occur again—becomes essential.
The Solution: lru_cache
Instead of manually managing a dictionary to store past results, Python provides a powerful built-in decorator: @lru_cache. By simply decorating your function, Python handles the caching logic for you.
from functools import lru_cache
@lru_cache(maxsize=128)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
The maxsize parameter determines how many recent calls to store. When fib(n) is called, Python first checks if the result is in the cache. If it is, it returns it instantly. If not, it executes the function and stores the result before returning it.
This simple addition transforms an algorithm into an algorithm, allowing you to calculate large values almost instantaneously. It is a perfect example of using Python’s standard library to handle complex optimization patterns with minimal code.
Key Takeaway: Use @lru_cache to eliminate redundant computations in recursive functions by automatically storing and reusing results for identical input arguments.