Why is climbing stairs the Fibonacci sequence?

The last move was either one step from n-1 or two steps from n-2, so ways(n) = ways(n-1) + ways(n-2). That is the Fibonacci recurrence with shifted base cases.

Why is plain recursion exponential?

The two recursive calls overlap heavily, so the same subproblem is recomputed many times and the call count grows like the golden ratio to the power n. Memoisation or a loop removes the repeats.

What is the best time and space complexity?

O(n) time and O(1) space using two rolling variables, since each value depends only on the previous two. A matrix-exponentiation approach reaches O(log n) multiplications.

What are the base cases?

ways(1) = 1 and ways(2) = 2. If you define ways(0) = 1, the recurrence works from n = 2 with no special cases.

How does it change if you can take 1, 2 or 3 steps?

Add a third term, ways(n-3), and keep three rolling variables. Space stays O(1).

Should I use memoisation or a bottom-up loop?

Bottom-up is safer in Python because memoised recursion hits the default recursion limit near n = 1000. Memoisation is fine for explaining the idea, then show the loop.

Climbing stairs: the DP that is Fibonacci

Interview QuestionsBy Ashish JangraUpdated 25 October 2026

ways(n) = ways(n-1) + ways(n-2), because the last move was either one step or two. That is Fibonacci. Written as plain recursion it is exponential; the same recurrence computed once per value is O(n), and since only the last two values are ever needed it is O(1) space.

Dynamic programmingCoding problemEasy

Step through it

Speed

What to watch

The call count roughly doubles per extra step — that is the overlap, measured.
Filling forwards computes each value exactly once.
Only the last two entries are ever read, which is why the table can go.

Say this out loud

"The last move was either a single step from n-1 or a double from n-2, so ways(n) = ways(n-1) + ways(n-2) with ways(1) = 1 and ways(2) = 2. It is Fibonacci. Naive recursion is exponential because the subproblems overlap, so I either memoise or fill a table forwards - and since only the last two entries are read, two variables are enough. O(n) time, O(1) space."

import functools, sys calls = 0 def naive(n): """Correct, and exponential: the subproblems overlap.""" global calls calls += 1 if n <= 2: return n return naive(n - 1) + naive(n - 2) print("done")

import functools, sys print("plain recursion:") for n in (10, 20, 25): calls = 0 v = naive(n) print(f" ways({n:>2}) = {v:>7,} calls: {calls:>9,}") print(" the call count grows exponentially, not linearly") @functools.lru_cache(maxsize=None) def memo(n): """Top-down: same recurrence, each value computed once.""" if n <= 2: return n return memo(n - 1) + memo(n - 2) def table(n): """Bottom-up: no recursion, so no stack limit.""" if n <= 2: return n best = [0] * (n + 1) best[1], best[2] = 1, 2 for i in range(3, n + 1): best[i] = best[i - 1] + best[i - 2] return best[n] def rolling(n): """Only the last two entries are ever read.""" if n <= 2: return n a, b = 1, 2 for _ in range(n - 2): a, b = b, a + b return b

import functools, sys @functools.lru_cache(maxsize=None) def memo(n): if n <= 2: return n return memo(n - 1) + memo(n - 2) def table(n): if n <= 2: return n best = [0] * (n + 1) best[1], best[2] = 1, 2 for i in range(3, n + 1): best[i] = best[i - 1] + best[i - 2] return best[n] def rolling(n): if n <= 2: return n a, b = 1, 2 for _ in range(n - 2): a, b = b, a + b return b n = 30 print() print(f"ways({n}):") print(f" memoised {memo(n):>8,} cache holds {memo.cache_info().currsize} entries") print(f" table {table(n):>8,} list of {n + 1} ints") print(f" rolling {rolling(n):>8,} 2 variables") print(" all agree:", memo(n) == table(n) == rolling(n)) print(" and they agree with the naive version at n=25:", naive(25) == rolling(25))

import functools, sys @functools.lru_cache(maxsize=None) def memo(n): if n <= 2: return n return memo(n - 1) + memo(n - 2) def table(n): if n <= 2: return n best = [0] * (n + 1) best[1], best[2] = 1, 2 for i in range(3, n + 1): best[i] = best[i - 1] + best[i - 2] return best[n] def rolling(n): if n <= 2: return n a, b = 1, 2 for _ in range(n - 2): a, b = b, a + b return b # The reason to prefer bottom-up when n is large. print() print("recursion limit:", sys.getrecursionlimit()) try: memo.cache_clear() memo(4_000) except RecursionError as e: print(" memo(4000) -> RecursionError:", str(e)[:40]) print(" rolling(4000) has", len(str(rolling(4_000))), "digits and no stack cost")

About the author

Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.

Climbing stairs: the DP that is Fibonacci

Step through it

What to watch

Say this out loud

Overview

Run it

Where the recurrence comes from

Why plain recursion is exponential

Four versions, in the order to present them

The follow-ups

Edge cases to raise

Sources and next steps

How the code works

How the code works

Change one thing

Where this runs

Check yourself