Upgrading Python Recursion with functools.lru_cache

Make Fibonacci fast—and understand what's happening under the hood

Hey there! If you've ever played with the Fibonacci sequence in Python, you probably know how painfully slow a naive recursive version can be. Let’s explore how functools.lru_cache can turn that recursion into lightning fast compute.

The problem: Fibonacci and slow recursion

Say you write this classic recursive function:

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

It’s simple and elegant. But try fib(40) or higher, and you'll wait... because it recombines the same subproblems again and again.

A quick fix with lru_cache

Here’s how we can upgrade it:

from functools import lru_cache

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

print(fib_cached(40))           # instant result
print(fib_cached.cache_info())  # shows hits & misses

With this decorator in place, repeated calls with the same n are cached. That means no redundant work. The function returns previously computed values instantly.

What does lru_cache actually do?

Under the hood, Python wraps your function in a helper that maintains a cache dict keyed by your arguments. When you call the function:

• If the key is already in the cache → return that result (cache hit).
• If not → run the function, store the result in cache, then return it (cache miss).

It also tracks usage order. When cache reaches its maxsize, the least recently used entry is evicted. This gives the “LRU” in the name. It uses a dict plus a linked‑list‑like structure to keep it efficient at O(1) costs [1].

Watching it in action

Try printing cache statistics:

print(fib_cached.cache_info())
# CacheInfo(hits=…, misses=…, maxsize=128, currsize=…)

A cache hit avoids a full recursive expansion and the difference can be dramatic. 100 × speedups are common for moderately large inputs:

import time
from functools import lru_cache


def fib(n: int) -> int:
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)


@lru_cache(maxsize=128)
def fib_cached(n: int) -> int:
    if n < 2:
        return n
    return fib_cached(n - 1) + fib_cached(n - 2)


if __name__ == "__main__":
    N: int = 40
    start = time.time()
    res = fib(N)
    end = time.time()

    start_cached = time.time()
    res_cached = fib_cached(N)
    end_cached = time.time()

    print(f"Result: {res}, took {end-start} seconds")
    print(f"Result (cached): {res_cached}, took {end_cached-start_cached} seconds")
    print(fib_cached.cache_info())

Output:

Result: 102334155, took 12.384701013565063 seconds
Result (cached): 102334155, took 3.910064697265625e-05 seconds
CacheInfo(hits=38, misses=41, maxsize=128, currsize=41)

Gotchas & best practices

• Hashable arguments only: Your function args must be hashable (like ints, tuples, strings). If you set typed=True, also 3 and 3.0 are cached separately [2].
• Cache size management: maxsize=None gives an unlimited cache (similar to @functools.cache in Python 3.9+)—but can grow in memory. If you only want fixed size, set a reasonable maxsize [1].
• Not for non‑deterministic functions: Don’t use it on functions that return different results on each call (e.g. current time, random), or functions with external side effects.

Custom implementation (if you’re curious)

Want to build your own version? One approach is using collections.OrderedDict, where you manually move items on access and evict oldest when full. It’s a great learning exercise.

TL;DR

Just apply @lru_cache to speed up recursion-heavy, deterministic computations.

Give it a try next time you have a slow recursive or repeat‑heavy function—just decorate it, print the cache info, and enjoy the speed‑boost.

References

1. Python Docs
2. Python lru_cache Usage Guide