16 Fibonacci Series Using Memoization

Fibonacci Series Using Memoization

The Fibonacci sequence is the classic first place where you feel the difference between a slow algorithm and a fast one. The rule is simple: each number is the sum of the two before it. Starting from 0, 1, we get 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, .... Formally, F(0)=0, F(1)=1, and F(n)=F(n-1)+F(n-2) for n ≥ 2.

The obvious way to compute F(n) is to translate that formula straight into a recursive function. It is beautifully short — and catastrophically slow. Memoization is the small, surgical fix that turns that same recursion from exponential into linear time, without you having to redesign the algorithm at all.

The intuition: stop re-solving the same subproblem

Picture the naive recursion for F(5). To get F(5) you need F(4) and F(3). But F(4) also needs F(3). So F(3) gets computed twice — and each of those recomputes F(2), and so on. The work explodes because the recursion tree keeps rediscovering answers it already found on another branch.

Memoization is the idea that you should compute each distinct answer exactly once and write it down. The word comes from memo — a note to self. Before doing any work for F(n), you glance at your notes (a cache). If the answer is already there, you return it instantly. If not, you compute it, store it, then return. This is top-down dynamic programming: the natural recursion drives the order, and the cache kills the duplication.

Precise definition

Memoization is an optimization technique where the results of expensive function calls are cached and returned when the same inputs occur again. It applies whenever a problem has two properties:

• Overlapping subproblems — the same inputs recur across the recursion tree (Fibonacci hits this hard).
• Optimal substructure / pure functions — a call's output depends only on its arguments, so a cached value is always still valid.

For Fibonacci, the cache is keyed by n. There are only n+1 distinct arguments (0..n), so once each is solved once, the total useful work is bounded by n+1. Here is the shape in code:

memo = {}
def fib(n):
  if n < 2: return n
  if n in memo: return memo[n]
  memo[n] = fib(n-1) + fib(n-2)
  return memo[n]

Worked example: counting the calls for F(5)

Let us count actual calls, because the numbers are the whole point.

Naive recursion. The number of calls to compute F(n) is 2·F(n+1) - 1. For F(5) that is 2·F(6) - 1 = 2·8 - 1 = 15 calls. Notice within that tree: F(3) is computed 2 times, F(2) 3 times, F(1) 5 times, F(0) 3 times. Pure waste.

Memoized. Walk the left spine first: fib(5)→fib(4)→fib(3)→fib(2)→fib(1)=1, fib(0)=0, so memo[2]=1. Returning up, fib(3) needs fib(1) — base case, no recursion. memo[3]=2. Then fib(4) needs fib(2), which is already in the memo — instant hit, no subtree. memo[4]=3. Finally fib(5) needs fib(3), another cache hit. memo[5]=5.

Each of fib(2)..fib(5) does real work exactly once; every second dependency is a cache hit. The 15 naive calls collapse to about 2n calls total. Step through the tree below and watch the cache hits prune whole branches.

Pitfalls and what an interviewer probes

• "What is the complexity, exactly?" Memoized Fibonacci is O(n) time (each of n+1 arguments is computed once, each in O(1) additional work) and O(n) space — the cache plus the recursion stack, which reaches depth n. Naive is O(φⁿ) time where φ ≈ 1.618. Best, worst, and average are all the same here because the input is a single integer n.
• Cache scope bug. A cache shared across separate top-level calls (a module-level dict, or a mutable default argument) is fine for a pure function but surprises people. A cache re-created inside a wrapper on every top-level call is fine too. The real trap is a mutable default argument in Python that accidentally persists — know why it does.
• Stack overflow. Because recursion depth is n, large n can blow the call stack (Python defaults near 1000). Interviewers love asking you to convert to the bottom-up tabulation form, which is iterative and avoids the stack entirely.
• Integer growth. F(n) grows exponentially, so for large n the numbers exceed 64-bit range. In Java/Go you must reason about overflow; Python big-ints hide it but the additions stop being O(1).

When it matters — and the trade-offs

Memoization is your default move whenever a recursive solution has overlapping subproblems: DP on strings (edit distance, LCS), grid paths, coin change, and countless interview problems. The win is dramatic — from exponential to polynomial — for the price of caching.

Against neighbouring approaches: bottom-up tabulation has the same O(n) time but often lower constant factors and no recursion stack, at the cost of computing every subproblem even if some are never needed (memoization is lazy — it only solves what the top call reaches). For Fibonacci specifically, you can go further: keep just the last two values in an iterative loop for O(n) time, O(1) space, dropping the cache entirely. And a fast-doubling / matrix-power method reaches O(log n) time. So memoization is not the theoretical optimum for Fibonacci — but it is the clearest illustration of the technique, and the one that generalizes to problems where no closed-form trick exists.

Key takeaways

• Memoization caches each distinct subproblem's result the first time it is computed, turning naive Fibonacci from O(φⁿ) into O(n) time, O(n) space.
• It works because Fibonacci has overlapping subproblems and is a pure function of n — there are only n+1 distinct answers to store.
• For F(5) the naive tree makes 15 calls; memoization collapses it to about 2n by serving repeats from the cache.
• Know the neighbours: bottom-up tabulation (same time, no stack), the two-variable O(1)-space loop, and O(log n) fast doubling — memoization teaches the pattern, not the fastest Fibonacci.