Python Program to Optimize Fibonacci Series Using Memoization

The Fibonacci sequence — where each number is the sum of the two before it (0, 1, 1, 2, 3, 5, 8, 13...) — is usually the first example anyone sees of recursion: a function that calls itself with a smaller version of the same problem until it reaches a simple base case it can answer directly. Written recursively, the n-th Fibonacci number is just "the (n-1)th number plus the (n-2)th number," which maps almost word-for-word onto code. The catch is that the naive recursive version is shockingly slow for anything beyond small inputs, which makes it a perfect case study for memoization — caching results so the same work never happens twice.

Naive Recursive Fibonacci (Slow)

def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)


print(fib_naive(10))

Output:

55

This works, but it is dramatically inefficient: computing fib_naive(n) calls itself twice, each of which calls itself twice again, and so on — the same sub-values like fib_naive(5) get recalculated thousands of times inside a single call to fib_naive(30). The time complexity is O(2^n), exponential, because the call tree roughly doubles in size with every increase in n. Try calling fib_naive(35) and you'll already notice a real delay; fib_naive(50) would take hours.

Memoized Fibonacci Using a Dictionary Cache

def fib_memo(n, cache={}):
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]


print(fib_memo(50))

Output:

12586269025

Each value from fib_memo(0) up to fib_memo(n) is now computed at most once and stored in cache, so any repeat call just looks the answer up instead of recomputing it. This takes the time complexity down from O(2^n) to O(n) — a linear amount of work — at the cost of O(n) extra memory to store the cache. fib_memo(50) returns instantly, where the naive version would still be running.

The Idiomatic Way: functools.lru_cache

from functools import lru_cache

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


print(fib_cached(50))

Output:

12586269025

The @lru_cache decorator does exactly the same thing as the manual dictionary cache — it keeps a lookup table keyed on the function's arguments — but without you writing the caching logic by hand, which is why it's the version you'll see most often in real Python code. Memoization is the technique behind a huge family of dynamic programming solutions: any time a recursive solution recomputes the same sub-problem repeatedly (not just Fibonacci — think grid paths, coin-change, or edit distance), caching those sub-results is usually the first optimization worth reaching for.