This Python script benchmarks the performance difference between two recursive implementations of the Fibonacci sequence: slow_fib(n): a naive recursive function (beautifully slow). fib(n): an optimized version using functools.lru_cache for memoization (blazing fast after the first call).

lru_cache_fibonacci.py

import time
from functools import lru_cache


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


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


if __name__ == "__main__":
    n = 40

    print(f"Calculating Fibonacci of {n} without memoization:")
    start_time = time.time()
    print(slow_fib(n))
    end_time = time.time()
    print(f"Function slow_fib took {end_time - start_time:.4f} seconds")
    print()

    print(f"Calculating Fibonacci of {n} using memoization:")
    start_time = time.time()
    fib.cache_clear()  # Clear cache before measuring
    print(fib(n))
    end_time = time.time()
    print(f"Function fib took {end_time - start_time:.4f} seconds")

Output:

Calculating Fibonacci of 40 without memoization:
102334155
Function slow_fib took 53.5771 seconds

Calculating Fibonacci of 40 using memoization:
102334155
Function fib took 0.0001 seconds