Fibonacci sequence: Three implementation strategies compared.
This example demonstrates three different approaches to computing the Fibonacci sequence, each illustrating important programming concepts. The Fibonacci sequence is one of the most famous sequences in mathematics and provides excellent examples of different algorithmic approaches.
Fibonacci Sequence
Mathematical Definition
The Fibonacci sequence is defined recursively as:
- F(0) = 1
- F(1) = 1
- F(n) = F(n-1) + F(n-2) for n > 1
Sequence Values
Sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
Mathematical Properties
- Golden ratio: Ratio F(n+1)/F(n) approaches φ ≈ 1.618
- Binet's formula: Closed-form expression exists
- Many applications: Nature, art, mathematics, computer science
Three Implementations
1. Iterative (<tt>fib_it</tt>)
Strategy: Use loop with two variables to track previous values
Algorithm:
if n <= 1: return 1
prev2 = 1, prev1 = 1
for i = 2 to n:
current = prev1 + prev2
prev2 = prev1
prev1 = current
return current
Characteristics:
- Time: O(n) - linear time
- Space: O(1) - constant space
- Efficiency: Most efficient
- Best for: Production code, large n
2. Recursive (<tt>fib_rec</tt>)
Strategy: Direct translation of mathematical definition
Algorithm:
Problem: Many redundant calculations!
Call tree for F(5):
F(5)
/ \
F(4) F(3)
/ \ / \
F(3) F(2) F(2) F(1)
... (many duplicate calls)
Characteristics:
- Time: O(2^n) - exponential! (terrible)
- Space: O(n) - call stack depth
- Redundancy: Calculates same values many times
- Best for: Educational purposes, small n only
3. Stack-based (<tt>fib_st</tt>)
Strategy: Simulate recursion using explicit stack
Algorithm:
stack.push({n, return_point=
P0})
while stack not empty:
item = stack.top()
if item.n <= 1:
item.result = 1
stack.pop()
else if item.return_point ==
P0:
stack.push({n-1, return_point=
P0})
else if item.return_point ==
P1:
item.f1 = result from previous call
stack.push({n-2, return_point=
P0})
else:
item.result = item.f1 + result from previous call
stack.pop()
Characteristics:
- Time: O(n) - similar to iterative
- Space: O(n) - explicit stack
- Educational: Shows how recursion works internally
- Best for: Understanding recursion mechanics
Complexity Comparison
| Implementation | Time | Space | Redundancy | Best For |
| Iterative | O(n) | O(1) | None | Production |
| Recursive | O(2^n) | O(n) | Massive | Education |
| Stack-based | O(n) | O(n) | None | Learning |
Performance Example
Computing F(40):
- Iterative: ~40 operations, instant
- Recursive: ~2^40 operations, very slow!
- Stack-based: ~40 operations, fast
Educational Value
Concepts Demonstrated
This example teaches:
- Algorithm design: Different approaches to same problem
- Performance analysis: Time/space complexity comparison
- Recursion mechanics: How call stacks work internally
- Stack data structures: Using stacks to simulate recursion
- Optimization: Why naive recursion is inefficient
Learning Outcomes
After studying this example, you understand:
- Why naive recursion can be inefficient
- How to optimize recursive algorithms
- How recursion is implemented internally
- When to use iterative vs recursive approaches
Optimizations
Memoization (Not Shown)
Can optimize recursive version with memoization:
memo = {}
fib_memo(n):
if n in memo: return memo[n]
if n <= 1: return 1
memo[n] = fib_memo(n-1) + fib_memo(n-2)
return memo[n]
Time: O(n) - each value calculated once Space: O(n) - memoization table
Matrix Exponentiation (Advanced)
Can compute F(n) in O(log n) time using matrix exponentiation:
[F(n+1)] [1 1]^n [1]
[F(n) ] = [1 0] [1]
Time: O(log n) - very fast!
Applications of Fibonacci
Nature
- Phyllotaxis: Leaf arrangement, flower petals
- Spiral patterns: Pine cones, sunflowers
- Growth patterns: Population growth models
Computer Science
- Algorithm analysis: Example of exponential recursion
- Dynamic programming: Classic DP example
- Golden ratio search: Optimization algorithms
Mathematics
- Number theory: Many interesting properties
- Combinatorics: Counting problems
- Graph theory: Fibonacci graphs
Usage
# Compute F(10) using all three methods
./fib 10
# Compare performance (recursive will be slow!)
./fib 20
# See exponential growth of recursive version
./fib 30 # Recursive takes much longer
Performance Warnings
⚠️ Warning: The recursive version is extremely slow for large n!
- F(30): Takes seconds
- F(40): Takes minutes
- F(50): Takes hours/days
Use iterative or stack-based for large values.
- See also
- fibonacci.C More comprehensive Fibonacci examples
-
tpl_arrayStack.H Stack implementation used for stack-based version
- Author
- Leandro Rabindranath León
Definition in file fib.C.
1.9.8