How to Build a Fast Fibonacci with Memoization in Python

If you’ve ever written the classic recursive Fibonacci and wondered why it crawls for larger n, the answer is repeated work: the same subproblems get recomputed over and over. In this guide, you’ll learn exactly how to build a fast Fibonacci with memoization in Python—cleanly, readably, and efficiently.

What is memoization (and why it helps)

Memoization is a simple optimization where you cache results of expensive function calls and return the cached result when the same inputs occur again. For Fibonacci, subproblems like fib(30) are needed many times in the naive recursion; caching turns exponential time into linear time.

The baseline (slow) recursive Fibonacci

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

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

his is easy to read but very slow for n > 35 or so.

The easiest memoization: functools.lru_cache

Python’s standard library gives you memoization in one line via @lru_cache.

from functools import lru_cache

@lru_cache(maxsize=None)  # unlimited cache; safe for Fibonacci
def fib(n: int) -> int:
    if n < 0:
        raise ValueError("n must be non-negative")
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

# Example
print(fib(50))   # 12586269025

from functools import lru_cache

@lru_cache(maxsize=None)  # unlimited cache; safe for Fibonacci
def fib(n: int) -> int:
    if n < 0:
        raise ValueError("n must be non-negative")
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

# Example
print(fib(50))   # 12586269025

Why this works: After the first call computes (and caches) fib(k) for all k ≤ n, later calls reuse the cached values instantly. Time complexity becomes O(n) and space complexity O(n) due to the cache and recursion stack.

Manual memoization with a dictionary (for full control)

If you’d like to avoid decorators or control the cache yourself, use a dict:

def fib_memo(n: int, memo: dict[int, int] | None = None) -> int:
    if n < 0:
        raise ValueError("n must be non-negative")
    if memo is None:
        memo = {0: 0, 1: 1}  # base cases

    if n in memo:
        return memo[n]

    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

# Example
print(fib_memo(50))  # 12586269025

def fib_memo(n: int, memo: dict[int, int] | None = None) -> int:
    if n < 0:
        raise ValueError("n must be non-negative")
    if memo is None:
        memo = {0: 0, 1: 1}  # base cases

    if n in memo:
        return memo[n]

    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

# Example
print(fib_memo(50))  # 12586269025

This approach is explicit and great for learning or customizing cache behavior (e.g., clearing it between runs).

Iterative alternative (fast without recursion)

Memoization pairs naturally with recursion, but you can also go iterative to avoid recursion depth and stack usage:

def fib_iter(n: int) -> int:
    if n < 0:
        raise ValueError("n must be non-negative")
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

def fib_iter(n: int) -> int:
    if n < 0:
        raise ValueError("n must be non-negative")
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

While not “memoization,” it’s equally O(n) time, O(1) space, and sometimes preferable in production.

Testing and small benchmarks

if __name__ == "__main__":
    # correctness
    for k in range(10):
        assert fib(k) == fib_memo(k) == fib_iter(k)

    # quick timing demo (optional)
    import time
    t0 = time.perf_counter()
    _ = fib(500)       # warm-up fill of cache
    t1 = time.perf_counter()
    _ = fib(500)       # now instant due to cache
    t2 = time.perf_counter()
    print("First call:", t1 - t0, "seconds")
    print("Second call:", t2 - t1, "seconds")

if __name__ == "__main__":
    # correctness
    for k in range(10):
        assert fib(k) == fib_memo(k) == fib_iter(k)

    # quick timing demo (optional)
    import time
    t0 = time.perf_counter()
    _ = fib(500)       # warm-up fill of cache
    t1 = time.perf_counter()
    _ = fib(500)       # now instant due to cache
    t2 = time.perf_counter()
    print("First call:", t1 - t0, "seconds")
    print("Second call:", t2 - t1, "seconds")

You’ll notice the first call does the work, and subsequent calls return almost immediately from the cache.

Common pitfalls to avoid

• Forgetting base cases (0 and 1) leads to infinite recursion or wrong results.
• Negative inputs: validate n or define behavior up front.
• Unbounded growth: with lru_cache(maxsize=None), the cache grows as you call larger n. This is fine for Fibonacci (one value per integer up to n), but be mindful in other problems.

You now know how to build a fast Fibonacci with memoization in Python using both the built-in lru_cache decorator and a manual dictionary approach. In most cases, @lru_cache is the simplest, most Pythonic solution. With these tools, you can comfortably build a fast Fibonacci with memoization in Python that’s both fast and clean—and you can adapt the same pattern to many other recursive problems. Finally, remember that you can build a fast Fibonacci with memoization in Python and still choose the iterative version in production if you prefer constant-space and no recursion limits.