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.