Fibonacci Number Solution

Problem

Given a non-negative integer n, return the nth Fibonacci number. The sequence starts at F(0) = 0 and F(1) = 1, and every subsequent number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, 21...

Input: n = 6
Output: 8
Explanation: The sequence indexed from zero gives F(6) = 8.

Intuition

The Fibonacci recurrence is defined in terms of itself, making recursion a natural fit — but pure recursion recomputes the same values exponentially. F(5) calls F(4) and F(3); F(4) then also calls F(3), duplicating work. Caching results (memoization) cuts each subproblem to one computation. Better still, since F(n) only ever needs the two immediately preceding values, there's no reason to store the entire history: a rolling pair of variables is enough to compute any Fibonacci number in constant space.

Approach 1 — Naive Recursion

Translate the definition directly into code: if n is 0 or 1, return n; otherwise return the sum of the two recursive calls.

If n <= 1, return n (base cases F(0)=0, F(1)=1).
Return fib(n - 1) + fib(n - 2).

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

Time: O(2^n) — each call spawns two more, producing an exponential tree of redundant recomputation.

Space: O(n) — the recursion stack grows to depth n before hitting a base case.

Approach 2 — Memoization (Top-Down DP)

Same recursive structure, but store each result in a cache the first time it is computed. Any future call for the same n returns the cached value immediately instead of branching again.

Initialize a memo table with -1 (unvisited).
If n <= 1, return n.
If memo[n] is already filled, return it.
Compute fib(n-1) + fib(n-2), store the result in memo[n], then return it.

1def fib(n: int) -> int:
2    memo = {}
3
4    def solve(k: int) -> int:
5        if k <= 1:
6            return k
7        if k in memo:
8            return memo[k]          # skip recomputation for already-seen values
9        memo[k] = solve(k - 1) + solve(k - 2)
10        return memo[k]
11
12    return solve(n)

Time: O(n) — each value from 0 to n is computed exactly once and cached.

Space: O(n) — the cache holds n+1 entries, and the recursion stack is still O(n) deep.

Approach 3 — Iterative Bottom-Up DP

Build from the base cases upward: start with F(0) and F(1), then repeatedly advance a rolling pair of variables until reaching F(n). No recursion, no table — just two integers.

If n <= 1, return n.
Set prev = 0 (representing F(0)) and curr = 1 (representing F(1)).
For each step from 2 to n: compute next_val = prev + curr, then shift prev = curr and curr = next_val.
Return curr.

1def fib(n: int) -> int:
2    if n <= 1:
3        return n
4    prev, curr = 0, 1
5    for _ in range(2, n + 1):
6        prev, curr = curr, prev + curr  # advance both in one step to avoid using a temp variable
7    return curr

Time: O(n) — a single loop from 2 to n.

Space: O(1) — only two integers regardless of how large n grows.

Complexity Summary

Approach	Time	Space	When to use
Naive Recursion	O(2^n)	O(n)	Never in production — useful only to illustrate why memoization matters
Memoization	O(n)	O(n)	When top-down structure is easier to reason about, or as a stepping stone toward iterative DP
Iterative Bottom-Up	O(n)	O(1)	Default choice — minimal overhead, easiest to read, optimal in both dimensions

Common Mistakes

Forgetting that F(0) = 0, not 1 — both base cases (n=0 and n=1) must be handled; returning 1 for n=0 shifts every Fibonacci number by one.
Overwriting prev before computing the sum — in Java/C++, writing prev = curr; curr = prev + curr sets curr to curr + curr instead of the true next Fibonacci. Always compute the new value first, or swap simultaneously as Python's tuple assignment allows.
Off-by-one in the loop range — the loop must run from 2 to n inclusive; starting at 1 or ending at n-1 returns the wrong Fibonacci number.
Initializing the memo array with 0 instead of -1 — since F(0) = 0, a zero-initialized cache cannot distinguish "unvisited" from "already computed as zero", causing the recursion to skip computing any node that would return 0.
Thinking recursion + memoization is always slower than iteration — both are O(n); the iterative version wins on space and avoids stack-overflow risk for large n, but memoization is not inherently slow.

Fibonacci Number — Solution