How to Implement Memoized Fibonacci in Python with functools.cache

Use functools.cache to memoize a recursive Fibonacci function, avoiding repeated computation and dramatically speeding up the calculation.

Easy Python 3.9+ Aug 9, 2026 Functions & basics 14 views 0 copies

fibonacci memoization functools cache recursion

Python code

13 lines

Python 3.9+

from functools import cache

@cache
def fibonacci(n: int) -> int:
    """Return the n-th Fibonacci number (0-indexed)."""
    if n < 2:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

if __name__ == "__main__":
    for i in range(10):
        print(f"fibonacci({i}) = {fibonacci(i)}")
    print(f"Cache info: {fibonacci.cache_info()}")

Output

stdout

fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(3) = 2
fibonacci(4) = 3
fibonacci(5) = 5
fibonacci(6) = 8
fibonacci(7) = 13
fibonacci(8) = 21
fibonacci(9) = 34
Cache info: CacheInfo(hits=8, misses=10, maxsize=None, currsize=10)

How it works

The @cache decorator automatically stores the return value for each argument combination. When the same n is requested again, the cached result is returned instead of recomputing the recursion tree. This turns the exponential-time naive recursion into an O(n) algorithm because each fibonacci(k) is computed at most once. The decorator is available in Python 3.9+ and is a thin wrapper around functools.lru_cache with an unlimited cache size. The cache_info() method exposes hit/miss statistics, useful for verifying memoization is working.

Common mistakes

Forgetting to import from functools (requires Python 3.9+; use lru_cache for older versions).
Calling the function with large n without realizing the cache persists across calls; clear it via fibonacci.cache_clear() if needed.
Expecting the naive recursion to be fast as-is; without @cache, fibonacci(40) already takes seconds.

Variations

Use @lru_cache(maxsize=128) if you want to limit cache size.
Implement memoization manually with a dictionary in the function closure.

Real-world use cases

Optimizing recursive dynamic programming problems in technical interviews or coding challenges.
Caching expensive function results in a Python service, such as repeated database queries or API calls within a process.
Speeding up repetitive heavy computations in data pipelines where the same inputs occur frequently.

How to Implement Memoized Fibonacci in Python with functools.cache

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Functions & basics

Tutorials

Quizzes

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Functions & basics

Keep learning

Tutorials

Quizzes