Memoization with functools.cache in Python

Memoization means storing the result of a function call, so that the next call with the same arguments returns the stored result instead of computing it again. functools.cache does this for you.

The program

from functools import cache

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

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

55
12586269025
354224848179261915075

How it works

• Without the cache, fib(n) calls fib(n - 1) and fib(n - 2), and each of those calls two more. The same small values are computed again and again, and the number of calls grows very fast. fib(50) would take hours.
• @cache keeps a dictionary from arguments to results. Each value of n is computed once. After that, the stored result is used.
• The arguments must be hashable (numbers, strings, tuples). A list argument raises a TypeError.

Counting the calls

This version counts how many times the function body runs, with and without the cache:

from functools import cache

calls = 0

def slow_fib(n):
    global calls
    calls += 1
    if n <= 1:
        return n
    return slow_fib(n - 1) + slow_fib(n - 2)

print(slow_fib(25), "computed in", calls, "calls")

calls = 0

@cache
def fast_fib(n):
    global calls
    calls += 1
    if n <= 1:
        return n
    return fast_fib(n - 1) + fast_fib(n - 2)

print(fast_fib(25), "computed in", calls, "calls")
print(fast_fib.cache_info())

75025 computed in 242785 calls
75025 computed in 26 calls
CacheInfo(hits=23, misses=26, maxsize=None, currsize=26)

The cache keeps every result until the program ends. If a function is called with many different arguments, use functools.lru_cache(maxsize=1000) instead, which keeps only the most recently used results.

Related programs: Memoization in Python without a library.