Course contentsShow
← Python
Lesson 328 of 1,0605. Advanced Iteration and ComprehensionsFree lesson

Caching Results for Recursive Performance

You will utilize memoization decorators to store and reuse function return values, significantly accelerating recursive and expensive computational tasks.

Caching Results for Recursive Performance

In this lesson, you’ll learn how to use memoization decorators to instantly speed up recursive functions by storing their results for reuse.

When writing recursive functions—such as calculating a Fibonacci number—you often end up re-calculating the exact same values over and over again. For instance, to find fib(5), your program calculates fib(3) multiple times as it branches down the tree. This leads to exponential time complexity, making your code crawl as the input grows.

Memoization is the strategy of "caching" these results. Instead of performing the same calculation twice, the function first checks a lookup table (the cache). If the result is there, it returns the stored value immediately. If not, it computes it and saves it for the future.

In Python, the most elegant way to implement this is using the lru_cache (Least Recently Used cache) decorator from the functools module. By adding @lru_cache above your function definition, Python handles the storage logic for you automatically.

Example: Speeding up Fibonacci

Without caching, the execution time for fib(40) would be noticeable. With the decorator, it is near-instant:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(40))

The @lru_cache decorator wraps your function in a layer that intercepts calls. Before your recursive logic runs, it looks for n in its internal dictionary. If found, it returns the value in constant time. This simple transformation changes a slow, redundant process into an efficient, linear-time operation. It is a powerful tool to keep in your belt whenever you encounter recursive algorithms that suffer from overlapping subproblems.

Key Takeaway: Use memoization decorators to transform slow, redundant recursive calculations into high-performance operations by storing and retrieving previously computed results.