Fibonacci Number
Fibonacci Number: compute F(n), where F(0) = 0, F(1) = 1, and every later term is the sum of the two before it.
- 0 <= n <= 30
- F(0) = 0, F(1) = 1
- F(n) = F(n - 1) + F(n - 2) for n > 1
Intuition
The recurrence names exactly two dependencies, so a full table is unnecessary — only the previous two values matter at any moment. Carrying that pair forward and updating it n times computes the answer in linear time with two variables. The plain recursive definition, by contrast, recomputes the same subproblems exponentially often, which is what makes this the standard illustration of why overlapping subproblems need memoising or flattening.
A recurrence that depends on a fixed number of previous terms can always be rolled into that many variables instead of a full table. The signal is a fixed, small look-back. Climbing Stairs, Min Cost Climbing Stairs, and House Robber are the same optimisation.
Approach
Before reading on: count how many times fib(2) is evaluated by the naive recursion for fib(6). Then work out how many previous values you actually need to keep, and write the update without a temporary variable.
Why naive recursion is exponential
Writing fib(n) = fib(n-1) + fib(n-2) directly produces a call tree whose node count grows like the Fibonacci numbers themselves, roughly φⁿ where φ ≈ 1.618. The cause is overlap: fib(n-2) is evaluated once inside fib(n-1) and again as the second branch, and that duplication compounds at every level. fib(40) makes over 300 million calls to compute a value that fits in an int. The problem is not recursion but the absence of memory between branches.
Flattening the recurrence into two variables
Because F(i) depends only on F(i-1) and F(i-2), the whole table can be collapsed to a rolling pair. Hold prev = F(0) = 0 and curr = F(1) = 1, then repeat prev, curr = curr, prev + curr for n - 1 steps; after the loop curr holds F(n). Python's simultaneous assignment evaluates the entire right-hand side before rebinding, so both updates use the old values. In C++ and Java a temporary is required, and overwriting prev first is the classic way to corrupt the sequence.
Base cases and cost
F(0) = 0 and F(1) = 1 must be handled before the loop, since the iteration starts from an already-formed pair. Returning n covers both at once, because F(0) is 0 and F(1) is 1. The loop then runs O(n) times with O(1) space, holding two numbers rather than a table of n + 1. A memoised recursion reaches the same O(n) time but pays O(n) space for the cache plus the call stack, so the iterative form is strictly better here — the memoised version is worth knowing as the general technique, not as the answer to this problem.
Solution & live demo
Common pitfalls
Naive recursion without memoisation
def fib(self, n):
if n < 2:
return n
return self.fib(n - 1) + self.fib(n - 2)prev, curr = 0, 1
for _ in range(2, n + 1):
prev, curr = curr, prev + currThe same subproblems are recomputed across branches, giving roughly φⁿ calls. It is correct but times out well before large n, because nothing carries results between the two recursive branches.
Updating the pair in sequence rather than simultaneously
prev = curr; curr = prev + curr;
int next = prev + curr; prev = curr; curr = next;
After the first assignment prev already holds the old curr, so the sum adds curr to itself and produces powers of two instead of Fibonacci numbers. Python's tuple assignment avoids this by evaluating the right side first.
Off-by-one in the loop range
for _ in range(2, n):
for _ in range(2, n + 1):
The pair starts at F(0) and F(1), so reaching F(n) needs iterations for indices 2 through n inclusive. Stopping at n - 1 returns F(n - 1).
Edge cases
Returned directly as 0 before the loop begins.
Returned directly as 1; the rolling pair is already correct.
One iteration produces 1, the sum of the two base cases.
F(30) = 832040, comfortably inside a 32-bit int.
Overwriting prev first feeds a corrupted value into the sum and derails every later term.