Algorithm

Fibonacci (Memoized)

Recursion Pattern

Fibonacci (Memoized)

Compute the n-th Fibonacci number again, but fix the exponential blow-up of the naive recursion by caching results. Given a non-negative integer n, return fib(n) with fib(0) = 0 and fib(1) = 1, using memoization so each distinct subproblem is computed at most once. Return the single integer.

CONSTRAINTS
  • 0 <= n <= 40 (now fast enough that larger n is fine)
  • fib(0) = 0, fib(1) = 1
  • Use O(n) extra space for the cache
EXAMPLE 1
Input: n = 0
Output: 0
Base case, returned before the cache is ever consulted.
EXAMPLE 2
Input: n = 6
Output: 8
0,1,1,2,3,5,8 — index 6 is 8. Each of fib(2)…fib(6) is computed exactly once and cached.
EXAMPLE 3
Input: n = 10
Output: 55
Same result as the naive version, but reached in about 10 computations instead of hundreds of calls.
EXAMPLE 4
Input: n = 40
Output: 102334155
Trivially fast with memoization; the naive recursion would make billions of calls for the same input.
What exactly gets stored in the memo?
A mapping from an input n to its computed fib(n). The key is whatever uniquely identifies a subproblem — for Fibonacci that is just the single integer n.
Does memoization change the answer?
No — it returns identical results to the naive recursion. It only removes recomputation, changing the running time from O(2ⁿ) to O(n).
Is this the same as dynamic programming?
Yes — this is top-down DP: recursion plus a cache of subproblem answers. Bottom-up DP fills the same answers iteratively into a table instead of via recursion.
Why avoid memo={} as a default argument?
A mutable default is created once and shared across every call to the function, so its contents leak between separate invocations. Pass the cache explicitly or use an outer structure to avoid surprising state.

The naive Fibonacci recursion is correct but exponential, because the two branches recompute the same subproblems over and over — fib(3) was calculated again and again across the tree, each time from scratch. The recursion was forgetting. Memoization is the fix: remember each answer the first time you compute it, and return the stored value on every later request. It is the smallest possible change to the code and it turns O(2ⁿ) into O(n).

The one idea: a cache the recursion consults

Keep a lookup table — call it memo — mapping n to fib(n). Before doing any work for a given n, check the memo. If the answer is already there, return it instantly and do not recurse. Otherwise compute it the normal way, store it, then return it. This is the exact same "spend memory to avoid repeated work" trade you saw in Two Sum, now applied to recursive calls instead of array scans.

python
def fib(n, memo={}):
    if n <= 1:                       # base cases unchanged
        return n
    if n in memo:                    # already solved? return the cached value
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)   # solve once...
    return memo[n]                   # ...and remember it
Why this collapses the tree

The first time each value fib(k) is requested, it recurses and gets stored. Every subsequent request for fib(k) hits the memo and returns immediately, pruning that entire branch of the call tree before it can grow. So instead of an exponential tree, the recursion computes each of fib(0), fib(1), …, fib(n) exactly once — n + 1 distinct subproblems, each costing constant work on top of two cache lookups. That is O(n) time. The price is O(n) space for the memo (plus O(n) call-stack depth on the first descent).

Worked Example:fib(5) with memoization
- fib(5) → needs fib(4) then fib(3).
- fib(4) → needs fib(3) then fib(2). This descends the left spine, computing and storing fib(2)=1, fib(3)=2, fib(4)=3 the first time each is seen.
- Now fib(5) asks for fib(3). It is already in the memo (= 2) — return instantly, no recursion. The whole right branch that the naive version re-expanded is skipped entirely.
- fib(5) = fib(4) + fib(3) = 3 + 2 = 5, each subproblem touched once.
Crucial Notein real code, prefer passing the memo explicitly (or using an outer dictionary) rather than a mutable default argument like memo={}. A default {} is created once and shared across all calls to fib, so it persists between separate top-level invocations — sometimes handy, often a subtle bug. The shape shown keeps the example short, but the professional habit is an explicit cache.
The pattern, extracted

Memoized recursion (also called top-down dynamic programming) is a two-line upgrade to any recursion with overlapping subproblems: (a) check the cache before computing, (b) fill the cache after computing. The slots to identify in a new problem: what uniquely identifies a subproblem (here, just n — so the key is n), and what the base cases are. Recognition signal: a naive recursion whose call tree revisits the same inputs (Fibonacci, climbing stairs, coin change, grid paths). When the subproblem key is a single integer marching in one direction, you can often flip this into a bottom-up loop filling an array — but the memoized recursion is the most direct expression, and it is the true bridge from plain recursion into dynamic programming.

O(2ⁿ) Naive Recursion
→
O(n) Time · O(n) Space Memoization