Implement Fibonacci with memoization in Python. What problem does memoization solve, and what is the time complexity before and after?

How to think about it

This one checks three things at once: do you know why naive recursion is slow, can you apply a decorator correctly, and can you state the before/after complexity? The strongest answers also name the iterative bottom-up version as the space-optimal alternative.

Why naive recursion explodes

The call tree for fib(5) recomputes the same subproblems over and over — every * below is wasted work:

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)  *
│   │   └── fib(1)
│   └── fib(2)      *
└── fib(3)           *
    ├── fib(2)       *
    └── fib(1)

Because every call branches into two and nothing is remembered, the cost is O(2ⁿ) — fib(40) alone makes over 300 million calls. Memoization fixes it by remembering each result, so every distinct n is computed exactly once: O(n) time, O(n) space.

A worked example

functools.lru_cache makes memoization a one-liner — it stores (n,) → result in a dict and serves repeats instantly:

from functools import lru_cache

# Memoised recursion — one decorator turns O(2ⁿ) into O(n)
@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

# Bottom-up iterative — O(n) time, O(1) space, no recursion at all
def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print("First 10        :", [fib_memo(i) for i in range(10)])
print("fib(100)        :", fib_iter(100))
print("memo == iter    :", fib_memo(100) == fib_iter(100))
print("cache after work:", fib_memo.cache_info())

First 10        : [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
fib(100)        : 354224848179261915075
memo == iter    : True
cache after work: CacheInfo(hits=108, misses=101, maxsize=None, currsize=101)

The cache_info line is the proof memoization worked: 101 misses (each n from 0 to 100 computed exactly once) against 108 hits (every other reference served straight from the cache). Without the cache, those 108 hits would each have triggered another exponential subtree. Note too that fib(100) is a 21-digit integer — Python’s arbitrary-precision ints carry it without overflow, where a fixed-width language would have wrapped around long ago.

The space-optimal version

def fib(n: int) -> int:
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

This keeps only the last two values, so it’s O(1) space, touches no call stack, and handles any n without a recursion limit — the right answer when n could be huge.

Approach	Time	Space	Recursion limit?
naive recursion	O(2ⁿ)	O(n) stack	yes
lru_cache recursion	O(n)	O(n)	yes
manual dict cache	O(n)	O(n)	yes
bottom-up iterative	O(n)	O(1)	no