Home / Python / Example programs / Functions and recursion

Python program: Fast recursive Fibonacci with memoisation

Make a slow recursive function fast by remembering its answers.

The code

from functools import lru_cache
import time

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

@lru_cache(maxsize=None)
def fib_fast(n):
    return n if n < 2 else fib_fast(n - 1) + fib_fast(n - 2)

t = time.perf_counter(); print(fib_slow(25)); slow = time.perf_counter() - t
t = time.perf_counter(); print(fib_fast(25)); fast = time.perf_counter() - t
print("cache is", "much faster" if fast < slow else "not faster")
print(fib_fast(200))

Output

75025
75025
cache is much faster
280571172992510140037611932413038677189525

How it works

The plain version recomputes the same values again and again. @lru_cache remembers every answer, so each value is computed once. Remembering results like this is called memoisation.

Learn the ideas behind it in the free lesson Pythonic Python.