There's a specific kind of frustration that happens when you write a piece of code that is logically perfect, but practically useless because it's too slow. I've been there more times than I'd like to admit. Usually, this happens with recursive functions where the program ends up calculating the exact same value thousands of times over.

Today we're looking at lru_cache from the functools module. "LRU" stands for Least Recently Used. In plain English, it's a decorator that remembers the results of a function for specific arguments. If you call the function again with those same arguments, Python doesn't re-run the logic; it just hands you the answer from memory. This is called memoization.

The Naive Approach to Recursion

Let's look at a classic example: calculating a Fibonacci number. I'll start with the most straightforward recursive implementation. It's clean, it's readable, and it's a performance nightmare.

def fibonacci(n):
    if n < 2:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(10)) # Fast enough
print(fibonacci(35)) # Noticeable lag
print(fibonacci(40)) # Now we're really waiting...

The problem here is the redundancy. To calculate fibonacci(40), the computer has to calculate fibonacci(39) and fibonacci(38). But to calculate fibonacci(39), it also has to calculate fibonacci(38). We are recalculating the same branches of the tree over and over again. It's an exponential explosion of work.

Letting functools Handle the Heavy Lifting

I could write my own dictionary to store these results, but that's boilerplate I don't want to maintain. Instead, I'll use lru_cache. It wraps the function and handles the storage logic for me behind the scenes.

from functools import lru_cache

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

print(fibonacci(100)) # Instantaneous

By adding that one line, we turned an exponential time complexity into linear time. I used maxsize=None here, which tells Python to grow the cache as needed. In a real production environment, you might set this to something like 128 to prevent the cache from eating up all your RAM if the input space is massive.

The Hashability Trap

Now, here is where I usually trip up when I'm rushing. I decided to expand this into a function that calculates a "score" based on a list of multipliers. I thought I'd just cache the result to speed up repeated calculations with the same list.

@lru_cache(maxsize=None)
def calculate_score(multipliers):
    print("Computing...") 
    return sum(multipliers) * 10

# This looks fine in my head
my_list = [1, 2, 3]
print(calculate_score(my_list))

If you run this, Python will throw a TypeError: unhashable type: 'list'. I forgot a fundamental rule of caching: lru_cache uses a dictionary internally to map arguments to results. Dictionary keys must be hashable. Since lists are mutable (they can change), they aren't hashable.

The fix is simple: use a tuple. Tuples are immutable and therefore hashable. If you're receiving a list from another part of your app, just cast it to a tuple before passing it into the cached function.

# The corrected version
my_list = [1, 2, 3]
print(calculate_score(tuple(my_list))) # Works perfectly

It's a small detail, but it's the difference between a crashing app and a fast one. Just remember: if you're caching a function, the arguments you pass in must be immutable.

📋 Practical Task

Exercise: Optimizing a Recursive Nested Category Total

You are building a system for an e-commerce store that calculates the total value of a product category. Some categories are nested inside others, and the calculation is recursive. Because the category tree is deep and often accessed repeatedly, the current implementation is too slow.

Your Task: Implement lru_cache to optimize the get_category_value function. Ensure that the function can handle repeated calls for the same category ID efficiently. Then, test it by calling the function for the same category twice and verifying that the "Calculating..." print statement only executes once.

from functools import lru_cache

# Simulated database of category values and their sub-category IDs
CATEGORY_DATA = {
    "Electronics": {"value": 100, "subs": ["Laptops", "Phones"]},
    "Laptops": {"value": 50, "subs": ["Gaming", "Ultrabooks"]},
    "Phones": {"value": 30, "subs": []},
    "Gaming": {"value": 20, "subs": []},
    "Ultrabooks": {"value": 15, "subs": []},
}

# TODO: Apply lru_cache here
def get_category_value(cat_id):
    print(f"Calculating value for {cat_id}...")
    data = CATEGORY_DATA.get(cat_id, {"value": 0, "subs": []})
    
    total = data["value"]
    for sub_id in data["subs"]:
        total += get_category_value(sub_id)
    
    return total

# Test your implementation
print(f"First call: {get_category_value('Electronics')}")
print("-" * 20)
print(f"Second call: {get_category_value('Electronics')}")