Fibonacci Number
Understanding the Problem
The definition gives the answer directly: each Fibonacci number is the sum of the two before it. The challenge is not figuring out what to compute, but how to compute it efficiently.
A recursive implementation that mirrors the definition recalculates the same subproblems repeatedly. Computing F(5) requires F(4) and F(3), but computing F(4) also requires F(3), so F(3) is computed twice. As n grows, this redundancy grows exponentially. Eliminating it is the entire point of the problem, and Fibonacci is the standard introduction to dynamic programming.
Key Constraints:
0 <= n <= 30→ The largest answer is F(30) = 832,040, which fits comfortably in a 32-bit integer, so overflow is not a concern. The small upper bound on n means even the exponential brute force runs in well under a second, but it still does roughly 2.7 million calls for n=30 against only 31 distinct subproblems, which motivates caching.
Approach 1: Recursive (Brute Force)
Intuition
Translate the mathematical definition into code: F(n) calls F(n-1) and F(n-2), each of which makes its own recursive calls, down to the base cases F(0) = 0 and F(1) = 1.
This is correct but inefficient. The recursion tree branches in two at every level, and the same subproblems are solved repeatedly. Computing F(5) computes F(3) twice, F(2) three times, and F(1) five times. The total number of calls grows exponentially with n.
Algorithm
- If
n <= 1, returnn(base cases: F(0) = 0, F(1) = 1). - Otherwise, return
fib(n - 1) + fib(n - 2).
Example Walkthrough
Let's trace through n = 4:
Code
- Time Complexity: O(2^n). Each call branches into two recursive calls. The recursion tree has roughly 2^n nodes.
- Space Complexity: O(n). The maximum depth of the recursion stack is n, since each call reduces n by at least 1.
The exponential time comes from recomputing the same subproblems. For F(30), the recursion makes about 2.7 million calls, but there are only 31 distinct subproblems. Storing each result the first time it is computed removes the redundancy entirely.
Approach 2: Memoization (Top-Down DP)
Intuition
The recursive approach solves only a handful of distinct subproblems but solves them many times over. Caching the result of each F(k) lets every later call return it in O(1) instead of recomputing the entire subtree.
This technique is called memoization. It keeps the top-down recursive structure but computes each F(k) at most once: the first call stores the result, and every subsequent call reads it back.
Algorithm
- Create a memo array to store computed results, initialized to -1.
- If
n <= 1, returnn. - If
memo[n]is already computed (not -1), return it. - Otherwise, compute
fib(n - 1) + fib(n - 2), store it inmemo[n], and return it.
Example Walkthrough
Code
- Time Complexity: O(n). Each subproblem F(0) through F(n) is computed exactly once and cached.
- Space Complexity: O(n). The memo array stores n+1 values, and the recursion stack goes n levels deep.
Computing the next Fibonacci number requires only the two most recent ones, so storing all n+1 values is unnecessary. The next approach builds up from the base cases while keeping only the last two values.
Approach 3: Iterative DP (Space Optimized)
Intuition
Instead of recursing top-down, build the sequence bottom-up. Start from F(0) = 0 and F(1) = 1, then compute F(2), F(3), ..., F(n) in order. Each step needs only the previous two values, so two variables suffice.
This removes both the recursion overhead and the memo array, giving O(n) time and O(1) extra space.
Algorithm
- Handle base cases: if
n <= 1, returnn. - Initialize two variables:
prev2 = 0(F(0)) andprev1 = 1(F(1)). - Loop from
i = 2ton: - Compute
current = prev1 + prev2. - Shift:
prev2 = prev1,prev1 = current. - Return
prev1.
Example Walkthrough:
Code
- Time Complexity: O(n). A single loop from 2 to n, with O(1) work per iteration.
- Space Complexity: O(1). Only three integer variables (prev2, prev1, current), regardless of n.
The O(n) iterative solution is the answer for this problem's constraints. The next approach reaches the answer in O(log n) time, which matters when n is large enough that a linear scan is the bottleneck.
Approach 4: Matrix Exponentiation (Logarithmic Time)
Intuition
The recurrence F(n) = F(n-1) + F(n-2) can be written as a single matrix multiplication. If we treat the pair of consecutive Fibonacci numbers as a column vector, then
Applying this transformation repeatedly gives a closed form. Let M = [[1, 1], [1, 0]]. Raising M to the power n produces the Fibonacci numbers directly:
So F(n) is the top-right entry of M^n. Computing M^n by multiplying M by itself n times would still be O(n), but matrix powers can be computed with fast exponentiation (exponentiation by squaring): M^n is built by repeatedly squaring, which takes only O(log n) matrix multiplications.
Algorithm
- Handle the base case: if
n <= 1, returnn. - Start with the result matrix set to the identity and the base matrix
M = [[1, 1], [1, 0]]. - While the exponent is greater than 0:
- If the lowest bit of the exponent is 1, multiply the result by the current base matrix.
- Square the base matrix.
- Shift the exponent right by one bit (integer divide by 2).
- After the loop, raising M to the power n places F(n) at index
[0][1]of the accumulated matrix. Return that entry.
Because each 2x2 multiply is constant work and the exponent halves each iteration, the total cost is O(log n).
Example Walkthrough
The result matrix is shown flattened as [a, b, c, d] for [[a, b], [c, d]]. After processing all bits of the exponent 6, the result holds M^6 = [[13, 8], [8, 5]], and index [0][1] is 8, which is F(6).
Code
- Time Complexity: O(log n). Each iteration halves the exponent, so the loop runs about log2(n) times, with constant work per iteration for the fixed-size 2x2 matrices.
- Space Complexity: O(1). A constant number of 2x2 matrices, regardless of n.
For this problem the O(n) iterative solution is already fast enough, and it is simpler to write correctly. The matrix method is the standard way to evaluate Fibonacci when n is large (for example, computing F(n) mod a prime for n in the billions), where O(log n) is the difference between feasible and not.