Memoization is a common optimization technique where repeatedly computed values are cached for quick lookup. While memoization can be achieved by a relatively simple modification to many recursive formulations, Python3's functools library implements automatic memoization in the form of an LRU (least recently used) cache as a function decorator.

The Fibonacci sequence (f_n = f_n-1+f_n-2) is a canonical example of a naive recursive function with exponential complexity.

The naive implementation is exponential. The second example using the LRU cache shows little growth up to moderately large values of n.

fibonacci.py

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

fibonacci_lru.py

from functools import *
 
@lru_cache(maxsize=None)
 
def fib(n):
    if n < 1:
        return n
    return fib(n-1) + fib(n-2)
 
print(fib(300))

The naive recursive implementation fails quickly as expected (at nearly a minute for n=40).