Memoization

Memoization saves the answer to every call so a repeated call is instant. The naive recursive Fibonacci recomputes the same values over and over, so its work explodes exponentially. Remembering results in a dictionary, or decorating the function with @functools.lru_cache, makes it linear. Reusing answers to smaller subproblems is the heart of dynamic programming.

How it reads

• slow_fib(20) makes over 20,000 calls to get one answer
• @lru_cache stores each result, so every n is computed only once
• fast_fib(80) finishes instantly; slow_fib(80) would never finish

Cloud tip: Memoization only helps when the same inputs come up again. Look for recursion with overlapping calls.