Python Decorator: Ways to Speed Up Recursions Using Built-in Caching

Recursive functions are elegant, but they can be brutally slow. A naive recursive Fibonacci implementation makes roughly 2ⁿ function calls for an input of n. Python's standard library provides two caching decorators — functools.lru_cache and functools.cache — that store results from previous calls and return them instantly on repeats. Adding one line of code can transform an exponential algorithm into a linear one. This article covers every built-in caching approach in depth: benchmarks, cache management methods, power-of-two maxsize tuning, thread safety behavior, the keyword argument order gotcha documented in the Python source, and the conditions under which caching is actively harmful. If you are new to Python decorators, that guide covers the underlying mechanics before you apply them to caching.

Why Recursion Is Slow Without Caching

The classic recursive Fibonacci function illustrates the problem. Each call branches into two more calls, and the same subproblems get recomputed over and over:

copyimport time


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


start = time.perf_counter()
result = fib(35)
elapsed = time.perf_counter() - start

print(f"fib(35) = {result}")
print(f"Time: {elapsed:.3f}s")

Computing fib(35) takes nearly 3 seconds because the function makes approximately 29 million calls. fib(3) alone gets called over 5 million times. Every one of those redundant calls does the same work and produces the same result. Caching eliminates the redundancy by storing each result the first time it is computed.

Manual Memoization with a Dictionary

Before reaching for a built-in decorator, it helps to understand the pattern. Memoization stores results in a dictionary keyed by the function's arguments:

copyimport time


def fib_memo(n: int, memo: dict[int, int] | None = None) -> int:
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n < 2:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]


start = time.perf_counter()
result = fib_memo(35)
elapsed = time.perf_counter() - start

print(f"fib_memo(35) = {result}")
print(f"Time: {elapsed:.6f}s")

From nearly 3 seconds to 21 microseconds. The dictionary stores each computed value, and subsequent calls with the same n return the stored result immediately. This is exactly what the built-in decorators automate.

functools.lru_cache: Bounded Caching

functools.lru_cache wraps a function with a Least Recently Used cache. When the cache reaches its maxsize, the entry that was accessed least recently gets evicted to make room:

copyfrom functools import lru_cache
import time


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


start = time.perf_counter()
result = fib(100)
elapsed = time.perf_counter() - start

print(f"fib(100) = {result}")
print(f"Time: {elapsed:.6f}s")

Without caching, fib(100) would require approximately 10²⁰ function calls and would never finish. With @lru_cache, it completes in under a millisecond because each value from fib(0) through fib(100) is computed exactly once.

The maxsize parameter defaults to 128. Setting it to None disables the size limit, making the cache grow without bound. Since Python 3.8, you can also apply @lru_cache without parentheses to use the default maxsize:

copyfrom functools import lru_cache


@lru_cache
def factorial(n: int) -> int:
    return n * factorial(n - 1) if n else 1


print(factorial(10))

functools.cache: Unbounded Caching

Python 3.9 introduced functools.cache as a simpler alternative to lru_cache(maxsize=None). It is a thin wrapper around a dictionary lookup with no eviction logic, making it slightly faster for unbounded use cases:

copyfrom functools import cache


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


print(fib(50))
print(fib(100))

cache_info() and cache_clear()

Both decorators add two management methods to the decorated function. cache_info() returns a named tuple with performance statistics, and cache_clear() empties the cache:

copyfrom functools import lru_cache


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


fib(50)
print(fib.cache_info())

fib.cache_clear()
print(fib.cache_info())

The hits field shows how many calls returned a cached result. The misses field shows how many calls computed a new result. For fib(50), there are 51 unique inputs (0 through 50), each computed once (51 misses), and 48 calls that hit the cache (the recursive second branch for each n >= 2).

Python 3.9 also added cache_parameters(), which returns the decorator's configuration as a plain dictionary:

copyfrom functools import lru_cache

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

fib(20)
print(fib.cache_info())        # hits, misses, maxsize, currsize
print(fib.cache_parameters())  # {'maxsize': 64, 'typed': False}

You can also access the original unwrapped function through __wrapped__, which is useful for testing or benchmarking without the cache:

copy# Call the original uncached function directly
print(fib.__wrapped__(10))

The typed Parameter

By default, lru_cache treats arguments of different types as equivalent if they compare equal. This means fib(3) and fib(3.0) share the same cache entry. Setting typed=True separates them:

copyfrom functools import lru_cache


@lru_cache(maxsize=128, typed=True)
def compute(x: int | float) -> int | float:
    print(f"  Computing for {x!r} (type: {type(x).__name__})")
    return x * 2


print(compute(3))
print(compute(3.0))
print(compute(3))

With typed=True, the integer 3 and the float 3.0 are cached separately. The third call returns the cached integer result without recomputing.

Recursion Depth and sys.setrecursionlimit

Python's default recursion limit is 1000. Even with caching, a deeply recursive first call can exceed this limit because the cache is empty and every level recurses before any result is stored. You can increase the limit with sys.setrecursionlimit, but the safer approach is to warm the cache incrementally:

copyfrom functools import cache


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


# Warm the cache in safe increments
for i in range(0, 5001, 250):
    fib(i)

# Now fib(5000) hits cached values, no deep recursion
print(f"fib(5000) has {len(str(fib(5000)))} digits")

Caching Beyond Fibonacci: Dynamic Programming

The caching decorators apply to any recursive algorithm with overlapping subproblems. Here are two additional examples. For a related pattern that pairs recursion with lazy evaluation, see the guide on recursive generators in Python.

Stair Climbing Problem

copyfrom functools import cache


@cache
def climb_stairs(n: int) -> int:
    """Count ways to climb n stairs taking 1, 2, or 3 steps at a time."""
    if n < 0:
        return 0
    if n == 0:
        return 1
    return climb_stairs(n - 1) + climb_stairs(n - 2) + climb_stairs(n - 3)


print(f"Ways to climb 10 stairs: {climb_stairs(10)}")
print(f"Ways to climb 30 stairs: {climb_stairs(30)}")

Minimum Edit Distance (Levenshtein)

copyfrom functools import cache


@cache
def edit_distance(s: str, t: str) -> int:
    """Compute the minimum edit distance between two strings."""
    if not s:
        return len(t)
    if not t:
        return len(s)
    if s[-1] == t[-1]:
        return edit_distance(s[:-1], t[:-1])
    return 1 + min(
        edit_distance(s[:-1], t),        # deletion
        edit_distance(s, t[:-1]),         # insertion
        edit_distance(s[:-1], t[:-1]),    # substitution
    )


print(edit_distance("kitten", "sitting"))
print(edit_distance("saturday", "sunday"))
print(edit_distance.cache_info())

Beyond the Decorator: Deeper Caching Strategies

The decorator approach solves the general case, but certain contexts demand more deliberate design. Four patterns come up repeatedly when the built-in decorators are not sufficient on their own.

Bottom-Up Iteration Instead of Top-Down Recursion

The decorator approach is top-down: start from the target value and recurse downward, caching results on the way back up. An alternative is to build the solution iteratively from the smallest subproblem upward. This eliminates the call stack entirely, removes any risk of hitting the recursion limit regardless of input size, and uses O(1) memory for problems where only the last few values are needed at each step:

copydef fib_iterative(n: int) -> int:
    """Bottom-up Fibonacci: O(n) time, O(1) memory, no call stack."""
    if n < 2:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b


# No recursion limit, no decorator overhead, no cache memory usage
print(fib_iterative(10_000))  # works without any sys.setrecursionlimit

For Fibonacci specifically, the iterative version uses two variables instead of a growing cache. For more complex DP problems — knapsack, longest common subsequence, coin change — the equivalent is filling a table row by row. The decorator is a shortcut that keeps the recursive structure readable; the iterative approach is what you reach for when the input range is unbounded or memory is constrained.

Class-Level Shared Cache

When a cached function is defined as a method on a class, @lru_cache and @cache behave differently than expected. Both decorators include self in the cache key, which means each instance maintains its own cache — and the instance cannot be garbage collected as long as the cache holds a reference to it. For algorithms shared across many instances, this means duplicated computation and memory growth proportional to instance count.

The idiomatic fix is to move the cached function to the module level or a static method, accepting arguments explicitly rather than through self:

copyfrom functools import cache


# Shared module-level cache — one cache for all callers
@cache
def _edit_distance(s: str, t: str) -> int:
    if not s:
        return len(t)
    if not t:
        return len(s)
    if s[-1] == t[-1]:
        return _edit_distance(s[:-1], t[:-1])
    return 1 + min(
        _edit_distance(s[:-1], t),
        _edit_distance(s, t[:-1]),
        _edit_distance(s[:-1], t[:-1]),
    )


class Spellchecker:
    def distance(self, word: str, candidate: str) -> int:
        # Delegates to shared cache — no per-instance duplication
        return _edit_distance(word, candidate)


a = Spellchecker()
b = Spellchecker()

# Both calls hit the same cache — computed once regardless of instance
print(a.distance("kitten", "sitting"))   # 3
print(b.distance("kitten", "sitting"))   # 3 — cache hit
print(_edit_distance.cache_info())       # hits=1, misses=1 (not hits=0, misses=2)

copyimport functools


class Spellchecker:
    def __init__(self):
        # Bind lru_cache to the instance in __init__ — no self in cache key,
        # no global strong reference, cache lifetime tied to instance lifetime
        self.distance = functools.lru_cache(maxsize=256)(self._distance_impl)

    def _distance_impl(self, word: str, candidate: str) -> int:
        """Core edit-distance logic — called through self.distance()."""
        if not word:
            return len(candidate)
        if not candidate:
            return len(word)
        if word[-1] == candidate[-1]:
            return self._distance_impl(word[:-1], candidate[:-1])
        return 1 + min(
            self._distance_impl(word[:-1], candidate),
            self._distance_impl(word, candidate[:-1]),
            self._distance_impl(word[:-1], candidate[:-1]),
        )


checker = Spellchecker()
print(checker.distance("kitten", "sitting"))   # 3
print(checker.distance.cache_info())            # per-instance cache
# When checker goes out of scope, cache and instance are collected together

Weak-Reference Caching for Large Return Values

Standard lru_cache holds strong references to cached return values, keeping them alive regardless of whether anything else in the program is using them. For functions that return large objects — NumPy arrays, DataFrames, parsed ASTs — this can hold gigabytes of memory that the garbage collector cannot reclaim even when the data is no longer needed anywhere else.

A manual cache backed by weakref.WeakValueDictionary stores weak references instead of strong ones. The cached value is kept alive as long as at least one strong reference exists elsewhere in the program. When the last strong reference drops, the garbage collector reclaims the object and the cache entry is removed automatically:

copyimport weakref


_parse_cache: weakref.WeakValueDictionary = weakref.WeakValueDictionary()


def parse_config(path: str) -> dict:
    """Cache parsed config objects weakly — GC can reclaim them."""
    if path in _parse_cache:
        return _parse_cache[path]
    # Simulate an expensive parse
    result = {"path": path, "data": list(range(1_000_000))}
    _parse_cache[path] = result
    return result


config = parse_config("/etc/app.conf")
print(len(_parse_cache))   # 1 — entry exists while config is in scope

del config
import gc; gc.collect()
print(len(_parse_cache))   # 0 — entry removed when strong reference dropped

The trade-off is that a cache hit is not guaranteed even for a key that was previously inserted — if no other strong reference exists at the time of the lookup, the entry will have been collected. Use weak-reference caching when the cost of recomputing is acceptable and memory pressure is the primary concern, not when every cache hit must be guaranteed.

Avoiding the Recomputation Window with an External Lock

The thread-safety nuance documented for lru_cache — that the wrapped function may execute more than once under concurrent load before the first result is cached — matters in a specific class of problems: expensive computations where double-execution has a real cost, such as a recursive function that reads from disk or makes a network call on cache miss. The decorator alone cannot prevent this. Wrapping the call in a threading.Lock serializes concurrent requests for the same key:

copyimport threading
from functools import lru_cache

_lock = threading.Lock()


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


def safe_recursive(n: int) -> int:
    """Serialize concurrent first-calls to prevent duplicate execution."""
    with _lock:
        return _expensive_recursive(n)


# safe_recursive ensures only one thread computes each unique n first
print(safe_recursive(50))  # 12586269025

This is intentional over-engineering for pure in-memory recursion — the lock contention cost would outweigh any benefit when the computation itself is microseconds. It is the right pattern when a cache miss triggers I/O or a database call, where executing twice has a real cost beyond CPU cycles.

When Not to Cache

Caching is not always appropriate. The Python documentation states that functions with side effects, functions that must produce distinct mutable objects on each call — such as generators and async functions — and impure functions like time() or random() are not suitable candidates (docs.python.org/3/library/functools.html). More broadly, avoid caching any function whose output depends on external state — a database query that might return different results over time, for instance, will silently return stale data once its result is cached. Also avoid caching functions that accept a huge number of unique inputs with no repetition, where the cache grows without ever producing a hit.

copyfrom functools import lru_cache


@lru_cache
def bad_candidate(items):
    """This will fail because lists are not hashable."""
    return sum(items)


try:
    bad_candidate([1, 2, 3])
except TypeError as e:
    print(f"Error: {e}")


# Fix: accept a tuple — convert at the call site before passing in
@lru_cache
def good_candidate(items: tuple[int, ...]) -> int:
    """items must be a tuple — lists are not hashable."""
    return sum(items)


my_list = [1, 2, 3]
print(good_candidate(tuple(my_list)))

Key Takeaways

1. Memoization eliminates redundant computation: Recursive functions with overlapping subproblems compute the same values repeatedly. Caching stores each result once and returns it on subsequent calls, reducing exponential time complexity to linear.
2. functools.lru_cache is the standard tool: Available since Python 3.2, it provides a configurable bounded cache with LRU eviction. The default maxsize is 128. Set it to None for unbounded caching.
3. functools.cache is the simpler option: Available since Python 3.9, it is equivalent to lru_cache(maxsize=None) but faster because it skips eviction bookkeeping. Use it for recursive algorithms where you know the input space fits in memory.
4. Use cache_info() to monitor performance: The hits, misses, maxsize, and currsize fields tell you how effectively the cache is working. High miss rates suggest the cache is too small or the function is not being called with repeated arguments.
5. Warm the cache to avoid hitting the recursion limit: For deeply recursive functions, call the function with incrementally larger inputs so that the cache builds up layer by layer. This avoids RecursionError without increasing sys.setrecursionlimit.
6. Consider bottom-up iteration when input range is unbounded: Iterative DP eliminates the call stack entirely, removes recursion limit risk at any input size, and can reduce memory to O(1) for rolling-window problems where only a few prior values are needed at each step.
7. Never apply @lru_cache directly to an instance method: The decorator includes self in the cache key, prevents garbage collection of instances, and duplicates computation across objects. Move the cached function to module level and delegate to it from the method.
8. Use WeakValueDictionary for functions returning large objects: Standard lru_cache holds strong references, keeping large return values in memory indefinitely. A manual cache backed by weakref.WeakValueDictionary allows the garbage collector to reclaim entries when no other strong reference exists.
9. Only cache deterministic, pure functions: Functions with side effects, non-deterministic output, or unhashable arguments are not suitable candidates for caching. The cached result must be correct for every future call with the same inputs.

Python's built-in caching decorators are the simplest and most reliable way to speed up recursive functions. One decorator, one import, and the algorithm's time complexity drops by orders of magnitude.