The Fibonacci and Climbing Stairs Patterns

The Fibonacci sequence and the Climbing Stairs problem are usually the very first dynamic programming problems anyone learns, and for good reason. They boil down to the exact same recurrence relation, they’re small enough to fully understand in one sitting, and they cleanly demonstrate why brute-force recursion can be catastrophically slow while a small change — remembering what you’ve already computed — makes it fast. Once this pattern clicks, you’ll start spotting it everywhere: any problem where the answer for size n depends only on the answers for a fixed number of smaller sizes.

Overview: How the Pattern Works

The Fibonacci sequence is defined by a simple recurrence: F(0) = 0, F(1) = 1, and for n >= 2, F(n) = F(n – 1) + F(n – 2). Each term depends only on the two terms immediately before it. The Climbing Stairs problem (a classic interview question) asks: if you can climb 1 or 2 steps at a time, how many distinct ways are there to reach the top of an n-step staircase? Think about how you could arrive at step n: your very last move was either a single step from step n – 1, or a double step from step n – 2. Every distinct way to reach step n – 1 becomes a distinct way to reach step n by adding one more single step, and every distinct way to reach step n – 2 becomes a distinct way to reach step n by adding one more double step. Those two sets of paths cannot overlap, since they differ in their final move, so the total count is simply their sum: ways(n) = ways(n – 1) + ways(n – 2). That is the Fibonacci recurrence wearing a different hat.

Overlapping subproblems

If you translate the recurrence directly into recursive Python, computing fib(5) calls fib(4) and fib(3). Computing fib(4) itself calls fib(3) and fib(2) — notice fib(3) gets computed again, entirely from scratch, with no memory of the first time. Zoom out further and fib(2) gets recomputed many times, fib(1) even more, and so on. This repeated recomputation of identical subproblems is called overlapping subproblems, and it is the first of the two properties that make a problem a good fit for dynamic programming.

Optimal substructure

The second property is optimal substructure: the answer to a bigger instance (fib(n) or ways(n)) can be built directly and correctly from the answers to smaller instances, with no need to reconsider or redo work at the larger scale. Because F(n) is exactly F(n-1) + F(n-2) — not an approximation, not something that needs adjustment — we can solve the small cases once, store them, and combine them to get every larger case. Whenever a problem has both properties, dynamic programming applies: either memoize the naive recursion (top-down) so repeated calls are answered from a cache instead of recomputed, or build the answers from the smallest case upward in a loop (tabulation, bottom-up), or, when only a fixed small window of previous answers is ever needed, collapse the table into a handful of rolling variables to save memory.

Time and Space Complexity

All of the implementations below solve the same recurrence, but their complexity differs wildly because of how much repeated work each one does and how much extra memory it spends to avoid that work.

Approach	Time	Space	Why
Naive recursion	O(1.618^n) (bounded by the golden ratio; often written loosely as O(2^n))	O(n)	The call tree branches into two recursive calls at almost every node, and the tree has depth n, so the total number of calls grows exponentially. The O(n) space is just the maximum depth of the call stack at any moment, not the total number of calls.
Memoized recursion (top-down)	O(n)	O(n)	Each distinct subproblem fib(k) for k from 0 to n is computed exactly once and then cached; every later call to the same k is an O(1) lookup. O(n) for the cache plus O(n) for the recursion stack.
Tabulation with a full array (bottom-up)	O(n)	O(n)	A single loop fills table[0..n] once, left to right, using only already-computed entries. No recursion, so no call-stack cost, but the table itself still uses O(n) memory.
Tabulation with two rolling variables	O(n)	O(1)	Since F(n) only ever needs the previous two values, there is no reason to keep the entire table; two variables updated in a loop are enough.

Examples

Example 1: Naive Recursive Fibonacci

This is the direct, unoptimized translation of the recurrence into code. It is correct, but as the complexity table above shows, it repeats enormous amounts of work.

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


results = [fib_naive(i) for i in range(10)]
print(results)

Output:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

fib_naive(0) and fib_naive(1) hit the base case directly and return 0 and 1. fib_naive(2) = fib_naive(1) + fib_naive(0) = 1 + 0 = 1. fib_naive(3) = fib_naive(2) + fib_naive(1) = 1 + 1 = 2, and so on — each value simply reuses the recurrence, recomputed from scratch every single time it is needed. For i from 0 to 9 this produces 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, matching the printed list. Try changing range(10) to range(35) and time it: it noticeably slows down, because the number of calls roughly grows by a factor of 1.618 with each increment of n.

Example 2: Top-Down Memoization with lru_cache

functools.lru_cache is the idiomatic way to add memoization to a recursive function without hand-writing a cache dictionary.

from functools import lru_cache


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


results = [fib_memo(i) for i in range(10)]
print(results)
print(fib_memo(50))

Output:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
12586269025

The first ten results match Example 1 exactly, because it is the same recurrence — only the reuse strategy changed. The real payoff shows on the second line: fib_memo(50) returns instantly with 12586269025, whereas fib_naive(50) would take an impractically long time, since it would make on the order of 1.618^50 (billions) of redundant calls. With memoization, computing fib(50) only ever computes fib(0) through fib(50) once each, 51 total calls that do real work.

Example 3: Bottom-Up Tabulation

Instead of recursing and caching, we can build the answer from the ground up in a simple loop, avoiding recursion (and its stack overhead) entirely.

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


results = [fib_tabulation(i) for i in range(10)]
print(results)

Output:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

For n = 9, table starts as [0, 1, 0, 0, 0, 0, 0, 0, 0, 0] after the first two entries are set. The loop then fills in table[2] = table[1] + table[0] = 1, table[3] = table[2] + table[1] = 2, table[4] = 3, table[5] = 5, table[6] = 8, table[7] = 13, table[8] = 21, and finally table[9] = 34, which is what gets returned. No call stack, no recursion — just one forward pass.

Example 4: Climbing Stairs, Space-Optimized

Since each term only ever needs the previous two, the full array can be replaced with two rolling variables, dropping space from O(n) to O(1).

def climb_stairs(n: int) -> int:
    if n <= 2:
        return n
    prev2, prev1 = 1, 2
    for step in range(3, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current
    return prev1


for n in range(1, 8):
    print(f"n={n}: {climb_stairs(n)} ways")

Output:

n=1: 1 ways
n=2: 2 ways
n=3: 3 ways
n=4: 5 ways
n=5: 8 ways
n=6: 13 ways
n=7: 21 ways

The base cases are handled directly: a 1-step staircase has exactly 1 way (a single step), and a 2-step staircase has exactly 2 ways (two single steps, or one double step). From n = 3 onward, prev2 and prev1 track ways(step - 2) and ways(step - 1) and slide forward one position each iteration, which is exactly the Fibonacci recurrence with different starting values (1, 2 instead of 0, 1).

How It Works, Step by Step

Walking through climb_stairs(5) from Example 4 makes the space-optimized loop concrete. The two variables prev2 and prev1 always hold ways(step - 2) and ways(step - 1) for whichever step the loop is about to compute.

Before loop	step	current = prev1 + prev2	prev2, prev1 after update
prev2 = 1 (ways(1)), prev1 = 2 (ways(2))	3	2 + 1 = 3	prev2 = 2, prev1 = 3
—	4	3 + 2 = 5	prev2 = 3, prev1 = 5
—	5	5 + 3 = 8	prev2 = 5, prev1 = 8

The loop stops after step = 5 because range(3, n + 1) with n = 5 produces 3, 4, 5. The function returns prev1, which now holds ways(5) = 8, matching the printed line n=5: 8 ways from Example 4. The function never allocates a list of length n; it only ever needs the last two answers, which is exactly what makes the O(1) space version possible.

Common Mistakes

Mistake 1: Off-by-one in the base cases

It is tempting to initialize both rolling variables to the same value, especially if you’re thinking of the sequence as starting at 0 like classic Fibonacci. But ways(1) and ways(2) are not the same number, and getting this wrong silently corrupts every answer from n = 2 onward.

def climb_stairs_buggy(n: int) -> int:
    prev2, prev1 = 1, 1  # BUG: treats ways(1) and ways(2) as both 1
    for step in range(3, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current
    return prev1


print(climb_stairs_buggy(2))  # prints 1, but the real answer is 2

Output:

1

For n = 2, range(3, 3) is empty, so the loop body never runs and the function returns prev1 unchanged — which was wrongly initialized to 1 instead of 2. The fix is to explicitly encode the two correct base cases before ever entering the loop:

def climb_stairs_fixed(n: int) -> int:
    if n <= 2:
        return n
    prev2, prev1 = 1, 2  # ways(1) = 1, ways(2) = 2
    for step in range(3, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current
    return prev1


print(climb_stairs_fixed(2))

Output:

2

Mistake 2: A mutable default argument used as an accumulator

A common way to enumerate every path (not just count them) is to pass along a growing list of moves and a shared results list through recursive calls. Using a mutable object (a list or dict) as a default argument is a classic Python trap: default argument objects are created exactly once, when the function is defined, and reused across every call that doesn’t explicitly override them.

def climb_stairs_paths(n: int, path: list = [], all_paths: list = []) -> list:
    if n == 0:
        all_paths.append(path.copy())
        return all_paths
    if n >= 1:
        path.append(1)
        climb_stairs_paths(n - 1, path, all_paths)
        path.pop()
    if n >= 2:
        path.append(2)
        climb_stairs_paths(n - 2, path, all_paths)
        path.pop()
    return all_paths


print(climb_stairs_paths(2))
print(climb_stairs_paths(2))  # BUG: all_paths from the first call is still attached

Output:

[[1, 1], [2]]
[[1, 1], [2], [1, 1], [2]]

The first call correctly returns the two ways to climb 2 stairs: [1, 1] and [2]. The path list is restored to empty by the matching pop() calls, so it looks harmless — but all_paths is never reset between calls, since it is the same default list object every time the function is called without an explicit third argument. The second call appends its own two paths onto the leftover results from the first call, silently doubling the list. The fix is to use None as the default and create fresh containers inside the function body:

def climb_stairs_paths(n: int, path: list | None = None, all_paths: list | None = None) -> list:
    if path is None:
        path = []
    if all_paths is None:
        all_paths = []
    if n == 0:
        all_paths.append(path.copy())
        return all_paths
    if n >= 1:
        path.append(1)
        climb_stairs_paths(n - 1, path, all_paths)
        path.pop()
    if n >= 2:
        path.append(2)
        climb_stairs_paths(n - 2, path, all_paths)
        path.pop()
    return all_paths


print(climb_stairs_paths(2))
print(climb_stairs_paths(2))

Output:

[[1, 1], [2]]
[[1, 1], [2]]

Now every call starts from a clean slate, and the two calls produce identical, independent results.

Best Practices

• Identify the recurrence first — write ways(n) in terms of smaller ways(k) on paper before writing any code. The code is just the recurrence plus a strategy for reuse.
• Start with the brute-force recursive version to prove correctness, then add memoization; it is usually a two-line change (a cache check and a cache write).
• Prefer bottom-up tabulation over top-down memoization when n can be large, since it avoids Python’s default recursion limit (around 1000) and the overhead of function calls entirely.
• Collapse a DP table to O(1) space only after you’ve verified the O(n)-space version is correct; premature space optimization makes bugs harder to spot.
• Use functools.lru_cache for a quick, idiomatic top-down cache instead of hand-rolling a dictionary, unless you need fine control over cache size or eviction.
• In interviews, state both the recursive-with-memo and iterative-tabulation solutions and their space/time trade-offs; interviewers often ask you to optimize space as a follow-up.
• Validate the input domain (for example, reject a negative n) at the boundary of the function rather than assuming callers are well-behaved.

Practice Exercises

1. Modify climb_stairs so that you can climb 1, 2, or 3 steps at a time (sometimes called the tribonacci pattern). What is the new recurrence, and what are the correct base cases for ways(0), ways(1), and ways(2)? Hint: ways(n) = ways(n - 1) + ways(n - 2) + ways(n - 3); with the right base cases, ways(5) should come out to 13.
2. Solve the classic "Minimum Cost Climbing Stairs" problem: given a list cost where cost[i] is the cost of stepping on stair i, and you may start on step 0 or step 1 and move 1 or 2 steps at a time, find the minimum total cost to reach one step past the last index. Hint: min_cost(i) = cost[i] + min(min_cost(i - 1), min_cost(i - 2)). For cost = [10, 15, 20], the expected answer is 15.
3. Implement fib two ways — top-down with memoization and bottom-up with O(1) space — and confirm they agree for every n from 0 to 20 (expected fib(20) = 6765). Then add a guard that raises ValueError for negative n in both versions.

Summary

• The Fibonacci recurrence F(n) = F(n - 1) + F(n - 2) and the climbing-stairs recurrence ways(n) = ways(n - 1) + ways(n - 2) are the same relation in disguise; recognizing this pattern is the real skill.
• Naive recursion is correct but exponential, roughly O(1.618^n) time, because it recomputes overlapping subproblems from scratch.
• Top-down memoization (a dict, or @lru_cache) turns it into O(n) time and O(n) space by caching each subproblem’s answer the first time it is computed.
• Bottom-up tabulation avoids recursion entirely, computing answers from the base cases upward in O(n) time and O(n) space.
• When only the last k answers are ever needed, replace the full table with k rolling variables to cut space from O(n) to O(1); this is the most common DP space optimization.
• Never use a mutable object as a default argument for an accumulator; use None and initialize fresh inside the function body.
• Double-check base cases carefully; an off-by-one in the first one or two values propagates through every subsequent term.