Recursive task with memoization: Fibonacci three ways

Coding Challenges
,
1

Problem. The naive recursive Fibonacci is exponential. Refactor it to O(n) using memoization.

Examples:

  • fib(0) → 0
  • fib(1) → 1
  • fib(10) → 55
  • fib(50) → 12586269025

Solution. Three approaches.

# Approach 1: manual dictionary memoization
def fib_memo(n, cache=None):
    if cache is None:
        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]


# Approach 2: functools.lru_cache
from functools import lru_cache

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


# Approach 3: bottom-up DP (no recursion)
def fib_dp(n):
    if n <= 1:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

All O(n) time. Approaches 1 and 2 use O(n) space for the cache; approach 3 uses O(1) space.

Gotchas.

  • Default mutable argument (cache={}) persists across calls in Python. Either use None sentinel or lru_cache.
  • Python’s default recursion limit is 1000. For large n, increase sys.setrecursionlimit or use the iterative DP.
  • lru_cache stores all results forever unless you call .cache_clear(). For production, bound the cache size.
  • Memoization applies whenever a problem has overlapping subproblems. Identify them by spotting repeated function calls with the same arguments.

Run: fibonacci memoization