1. Introduction
The Fibonacci sequence is perhaps the most widely known recurrence in mathematics and computer science. First described in Western mathematics by Leonardo of Pisa (Fibonacci) in 1202, the sequence arises naturally in diverse areas from population modeling to financial markets to the structure of sunflowers.
"The Fibonacci sequence is the simplest and most important example of a dynamic programming problem. If you understand how DP applies here, you can apply it anywhere." -- Steven Skiena, The Algorithm Design Manual
Computing Fibonacci numbers serves as the ideal first example of dynamic programming because it clearly demonstrates the transition from an exponential recursive solution to a linear iterative one, illustrating the core DP concepts of overlapping subproblems and optimal substructure.
2. Problem Definition
The Fibonacci sequence is defined by the recurrence:
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) for n >= 2
The first several terms are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| F(n) | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 |
3. Naive Recursion
The most direct translation of the mathematical definition into code:
functionfib(n): if n <= 1: return n returnfib(n - 1) + fib(n - 2) While elegant, this implementation is catastrophically inefficient. Computing fib(50) would require over 10^10 function calls and take minutes or hours on modern hardware. The problem is that the same values are recomputed an exponential number of times.
4. The Recursion Tree
The recursion tree for fib(5) reveals the source of inefficiency:
fib(5) / \ fib(4) fib(3) / \ / \ fib(3) fib(2) fib(2) fib(1) / \ / \ / \ fib(2) fib(1) fib(1) fib(0) fib(1) fib(0) / \ fib(1) fib(0) Notice that fib(3) is computed 2 times, fib(2) is computed 3 times, and fib(1) is computed 5 times. As n grows, this redundancy explodes exponentially.
Key Observation: The tree has approximately 2^n nodes, yet there are only n+1 unique subproblems (fib(0) through fib(n)). Dynamic programming eliminates this redundancy by solving each subproblem exactly once.
Call Count Analysis
| Subproblem | Times Computed (Naive) | Times Computed (DP) |
|---|---|---|
| fib(5) | 1 | 1 |
| fib(4) | 1 | 1 |
| fib(3) | 2 | 1 |
| fib(2) | 3 | 1 |
| fib(1) | 5 | 1 |
| fib(0) | 3 | 1 |
| Total calls | 15 | 6 |
5. Optimal Substructure and Overlapping Subproblems
The two hallmarks of a dynamic programming problem are both present:
- Optimal substructure: The solution to
F(n)is directly composed of solutions to smaller subproblemsF(n-1)andF(n-2). There is no "choice" to optimize here -- the structure is additive. - Overlapping subproblems: As the recursion tree shows, the same subproblems (such as
F(3)andF(2)) are solved multiple times across different branches of the recursion.
These properties guarantee that dynamic programming will yield an efficient solution by storing and reusing previously computed results.
6. Top-Down (Memoization)
Memoization adds a cache to the recursive solution. Before computing a value, we check if it has already been computed and stored.
functionfibMemo(n, memo): if n <= 1: return n if memo[n] != -1: return memo[n] memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo) return memo[n]// Usage:memo = array of size (n+1), filled with -1result = fibMemo(n, memo) With memoization, each subproblem is computed exactly once. Subsequent calls with the same argument return the cached value in O(1) time. The recursion effectively becomes a linear chain of calls from fib(n) down to fib(0).
7. Bottom-Up (Tabulation)
The bottom-up approach fills a table iteratively, starting from the base cases and building up to the target value.
functionfibDP(n): if n <= 1: return n dp = array of size (n + 1) dp[0] = 0 dp[1] = 1for i = 2to n: dp[i] = dp[i - 1] + dp[i - 2] return dp[n] This approach eliminates recursion entirely, avoiding stack overflow for large values of n. It processes subproblems in a natural order from smallest to largest.
8. Space Optimization
Since F(n) depends only on F(n-1) and F(n-2), we do not need to store the entire table. Two variables suffice:
functionfibOptimized(n): if n <= 1: return n prev2 = 0// F(0) prev1 = 1// F(1)for i = 2to n: current = prev1 + prev2 prev2 = prev1 prev1 = current return prev1This reduces space complexity from O(n) to O(1) while maintaining O(n) time complexity. This is a common optimization technique in DP problems where only a fixed window of previous states is needed.
Optimization Pattern: Whenever a DP recurrence depends on only the last k states, the space can be reduced from O(n) to O(k). For Fibonacci, k = 2, so O(1) space suffices.
9. Worked Example
Let us trace the bottom-up computation of F(7) = 13.
Tabulation Trace
| Step | i | dp[i-2] | dp[i-1] | dp[i] = dp[i-1] + dp[i-2] |
|---|---|---|---|---|
| Base | 0 | -- | -- | 0 |
| Base | 1 | -- | -- | 1 |
| 1 | 2 | 0 | 1 | 1 |
| 2 | 3 | 1 | 1 | 2 |
| 3 | 4 | 1 | 2 | 3 |
| 4 | 5 | 2 | 3 | 5 |
| 5 | 6 | 3 | 5 | 8 |
| 6 | 7 | 5 | 8 | 13 |
Space-Optimized Trace
| Iteration | prev2 | prev1 | current |
|---|---|---|---|
| Initial | 0 | 1 | -- |
| i = 2 | 1 | 1 | 1 |
| i = 3 | 1 | 2 | 2 |
| i = 4 | 2 | 3 | 3 |
| i = 5 | 3 | 5 | 5 |
| i = 6 | 5 | 8 | 8 |
| i = 7 | 8 | 13 | 13 |
Final answer: F(7) = 13.
10. Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Naive Recursion | O(2^n) | O(n) stack |
| Top-Down (Memoization) | O(n) | O(n) |
| Bottom-Up (Tabulation) | O(n) | O(n) |
| Space-Optimized | O(n) | O(1) |
| Matrix Exponentiation | O(log n) | O(1) |
The naive approach grows as O(phi^n) where phi is the golden ratio (approximately 1.618). The DP approaches reduce this to O(n). For even faster computation, matrix exponentiation can compute F(n) in O(log n) time using the identity that the matrix [[1,1],[1,0]]^n gives F(n).
11. Variations and Extensions
Tribonacci Numbers
Extend the recurrence to three terms: T(n) = T(n-1) + T(n-2) + T(n-3), with base cases T(0) = 0, T(1) = 0, T(2) = 1. The same DP techniques apply, using three variables for space optimization.
Fibonacci Modulo M
Computing F(n) mod M is common in competitive programming to avoid overflow. The Pisano period (the period of F(n) mod M) allows extremely large Fibonacci numbers to be computed modularly.
Generalized Fibonacci
The sequence G(n) = a * G(n-1) + b * G(n-2) with arbitrary coefficients a and b generalizes the Fibonacci recurrence. Matrix exponentiation extends naturally to this case.
Climbing Stairs Problem
A classic interview problem: count the ways to climb n stairs taking 1 or 2 steps at a time. The answer is exactly F(n+1), demonstrating how Fibonacci appears in disguise in many problems.
12. Applications
- Algorithm analysis: Fibonacci numbers appear in the analysis of Euclid's GCD algorithm (worst case) and AVL tree heights.
- Data structures: Fibonacci heaps use the sequence in their amortized analysis, achieving optimal bounds for priority queue operations.
- Financial modeling: Fibonacci retracement levels are used in technical stock market analysis to predict support and resistance levels.
- Nature and biology: Phyllotaxis (leaf arrangement), nautilus shells, and branching patterns in trees follow Fibonacci-related proportions.
- Coding theory: Fibonacci coding is a universal code used in data compression.
- Competitive programming: Fibonacci-type recurrences are building blocks for solving more complex DP problems.
13. References
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to Algorithms (4th ed.). MIT Press, 2022. Chapter 14: Dynamic Programming.
- Skiena, S. S. The Algorithm Design Manual (3rd ed.). Springer, 2020.
- Knuth, D. E. The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley, 1997.
- Koshy, T. Fibonacci and Lucas Numbers with Applications. Wiley, 2001.