What Are Fibonacci Numbers? The Dynamic Programming Pattern Every Interview Borrows

Climbing Stairs. House Robber. Decode Ways. Three problems that look unrelated, feel completely different, and contain the exact same recurrence underneath. You have probably solved at least one of them without realizing you just solved all of them. Every DP problem where the current state depends on a fixed number of previous states is Fibonacci in a Halloween costume.

The sequence itself is almost beside the point. What matters is the structure: overlapping subproblems, a two-state transition, and a space optimization that takes you from O(n) down to O(1). Learn this one pattern cleanly and a whole category stops feeling like a guessing game.

The Sequence, Precisely

Each Fibonacci number is the sum of the two before it:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)  for n >= 2

The first dozen values:

n	F(n)
0	0
1	1
2	1
3	2
4	3
5	5
6	8
7	13
8	21
9	34
10	55

Simple enough. The trouble starts when you try to compute F(50) the obvious way.

Why Naive Recursion Collapses

Your first instinct is to translate the definition directly into code:

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

This works. It is also catastrophically slow. Slower than you think. Slower than your interviewer wants to find out.

To compute fib(5), you call fib(4) and fib(3). To compute fib(4), you call fib(3) again. Then fib(3) calls fib(2) twice. For fib(50), the same subproblems get recomputed billions of times. The same work, over and over, from scratch, as if your program has the memory of a goldfish.

The recursive tree grows exponentially: O(2^n) time. fib(50) makes roughly 2^50 function calls. That is about a quadrillion calls. Your interviewer will be retired by the time it finishes.

Fibonacci recursive call tree for fib(5), showing fib(3) computed twice and fib(2) computed three times, highlighted in red

Space complexity is O(n) because the deepest call stack is n frames deep. This is the overlapping subproblems property in action: a naive recursive solution recomputes the same subproblem from scratch every single time.

Me: computing fib(50) recursively. My computer: "I've been working on this since 5pm." Friend: "But it's 4pm."

Your processor's entire sense of time, after you call naive fib(50) and hit enter.

Memoization: Stop Recomputing

The fix is almost embarrassingly simple. If you already computed fib(3), store it and reuse it. This is memoization, the top-down approach to dynamic programming.

from functools import lru_cache

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

Each value from 0 to n gets computed once, cached, and returned in O(1) when needed again. Time drops to O(n). Space is O(n) for the cache plus O(n) for the call stack.

Without lru_cache, you pass a dictionary manually:

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

You still think recursively, but each subproblem is solved exactly once. The recursive tree becomes a DAG. The quadrillion calls become n calls. Your interviewer stops checking their watch.

Tabulation: Bottom-Up and O(1) Space

Instead of starting at F(n) and recursing down, start at F(0) and build up. This is bottom-up dynamic programming, also called tabulation.

def fib(n: int) -> int:
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Time: O(n). Space: O(n) for the array.

But look at the loop. Each iteration only needs the previous two values. You do not need to keep the whole array around.

def fib(n: int) -> int:
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

Time: O(n). Space: O(1). This is the answer you want to land on in an interview. No recursion, no extra memory, one clean loop. The kind of solution that makes your interviewer nod and write something positive.

Can We Go Even Faster?

Yes. Matrix exponentiation computes F(n) in O(log n) time using the identity:

[F(n+1)]   [1 1]^n   [F(1)]
[F(n)  ] = [1 0]   * [F(0)]

Raise a 2x2 matrix to the nth power with repeated squaring and you get F(n) in O(log n), O(1) space. In practice, interviewers almost never expect this. The O(n) iterative solution is the target. Mention matrix exponentiation if they probe for "can you do better," but do not lead with it unless the constraints push n up to 10^18. Otherwise you are solving a problem nobody asked for.

Why Interviewers Use Fibonacci for Dynamic Programming

The sequence is not the point. Fibonacci is the canonical example of overlapping subproblems and optimal substructure, the two properties that define dynamic programming.

Every time you draw the recursive tree for fib(5) and see that fib(3) appears twice, you are seeing exactly why memoization works. That insight transfers directly to the most common interview variants:

Climbing Stairs (LeetCode 70): How many ways to reach step n taking 1 or 2 steps? ways(n) = ways(n-1) + ways(n-2). The story changed. The recurrence did not.
House Robber (LeetCode 198): Max money you can rob without hitting adjacent houses. rob(n) = max(rob(n-1), rob(n-2) + house[n]). Two previous states, a max operator instead of addition.
Decode Ways (LeetCode 91): The recurrence branches on whether one-digit or two-digit chunks are valid. Still two previous states feeding the current one.
Tribonacci Number (LeetCode 1137): Three previous states instead of two. Same technique, wider look-back window.

Once you see Fibonacci cleanly, these stop feeling like new problems. They are the same structure wearing different hats. This is not a coincidence. It is the point.

The Transition Is the Whole Game

What makes a problem Fibonacci-shaped? The current state depends on a fixed, small number of previous states, and those states are computed the same way every time.

The process is always:

Identify what state you are computing.
Figure out which previous states feed into it.
Write the recurrence.
Add memoization or convert to iteration.
Space-optimize if the look-back window is fixed.

If your look-back window is a fixed size (2, 3, or k), you can drop to O(k) space. If the window varies based on input, you usually cannot. That is the key question to ask before implementing.

The Growth Rate (and Why the Naive Solution Fails Fast)

Consecutive Fibonacci numbers converge to a ratio of approximately 1.618, the golden ratio (phi). This means F(n) grows like phi^n divided by sqrt(5). That is exactly why naive recursion is O(phi^n), sometimes written as O(2^n) since the two are in the same order class.

It also explains why the sequence grows so fast. F(50) is over 12 billion. Computing it naively means roughly phi^50 function calls. The math connects directly to the performance problem you are fixing. It is not just a slow algorithm. It is a structurally broken one, and understanding why is what the interviewer actually wants to see.

What the Interviewer Is Watching

If you write the naive recursive solution and stop, you have shown you can transcribe a math definition. Congrats.

If you write memoized recursion, you have shown you know DP exists.

If you write the iterative O(1) space solution, explain the state transition clearly, and proactively mention the space optimization before being asked, you have shown you can think in recurrences. That progression, not the code itself, is what the interviewer scores.

One practical note for Python: the default recursion limit is 1,000 frames. For large n, the memoized recursive approach hits RecursionError. Prefer the iterative solution in an interview unless the problem is small and explicitly asks for recursion. Finding this out mid-interview is not fun for anyone.

Key Takeaways

F(n) = F(n-1) + F(n-2), with F(0) = 0 and F(1) = 1.
Naive recursion is O(2^n) because subproblems repeat exponentially.
Memoization solves each subproblem once: O(n) time, O(n) space.
Tabulation with a rolling window: O(n) time, O(1) space. This is the target answer.
Matrix exponentiation gives O(log n) but is rarely expected.
Climbing Stairs, House Robber, Tribonacci, and Decode Ways all use the same two-state recurrence.
The skill being tested is writing the recurrence and explaining the progression out loud, not knowing the sequence.

Knowing the answer is not enough if you cannot explain your reasoning. SpaceComplexity runs voice-based mock interviews that score your communication and problem-solving together, the same way a real interviewer does.