Just For Fun 01: Fibonacci Sequence
Three Approaches to Computing the Famous Sequence
By the end of this lesson, you will be able to:
Introduction
The Fibonacci sequence is one of the most famous sequences in mathematics, appearing in nature, art, and computer science. Each number is the sum of the two preceding ones: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144…
In this lesson, we’ll explore three different computational approaches to generate Fibonacci numbers, each with unique advantages and trade-offs.
Key Concepts
💡 Concept 1: Mathematical Definition
The Fibonacci sequence is defined as: - F(0) = 0 - F(1) = 1
- F(n) = F(n-1) + F(n-2) for n > 1
This recursive definition leads naturally to our first implementation approach.
Example:
# Mathematical definition
# F(5) = F(4) + F(3) = 5
# F(4) = F(3) + F(2) = 3
# F(3) = F(2) + F(1) = 2💡 Concept 2: Computational Complexity
Different algorithms have different time complexities: - Recursive: O(2^n) - exponential, very slow for large n - Iterative: O(n) - linear, efficient for reasonable n - Binet’s Formula: O(1) - constant time, but limited by floating-point precision
Example:
# Time comparison for F(40):
# Recursive: ~1.6 billion operations
# Iterative: ~40 operations
# Binet's: ~5 operationsInteractive Examples
Example 1: Recursive Fibonacci
What this code does: This implements the mathematical definition directly using recursion. Each function call splits into two more calls, creating a tree-like computation structure. While elegant, it’s very inefficient for large numbers.
Example Code:
def fibonacci_recursive(n):
"""Calculate Fibonacci number using recursion"""
if n <= 1:
return n
return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)
# Test with small numbers (try 10, 15, 20)
for i in range(11):
print(f'F({i}) = {fibonacci_recursive(i)}')Example 2: Iterative Fibonacci
What this code does: This approach builds up the sequence from the bottom, keeping track of only the last two numbers. It’s much more efficient than recursion, using O(n) time and O(1) space.
Example Code:
def fibonacci_iterative(n):
"""Calculate Fibonacci number using iteration"""
if n <= 1:
return n
a, b = 0, 1
for i in range(2, n + 1):
a, b = b, a + b
return b
# Test with larger numbers (try 50, 100)
for i in [10, 20, 30, 40, 50]:
print(f'F({i}) = {fibonacci_iterative(i)}')
# Show the sequence
print("\nFirst 20 Fibonacci numbers:")
fib_sequence = [fibonacci_iterative(i) for i in range(20)]
print(fib_sequence)Example 3: Binet’s Formula
What this code does: This uses Binet’s closed-form formula to calculate Fibonacci numbers directly using the golden ratio. It’s mathematically elegant and theoretically O(1), but limited by floating-point precision for very large numbers.
Example Code:
import math
def fibonacci_binet(n):
"""Calculate Fibonacci number using Binet's formula"""
if n <= 1:
return n
# Golden ratio
phi = (1 + math.sqrt(5)) / 2
psi = (1 - math.sqrt(5)) / 2
# Binet's formula
result = (phi**n - psi**n) / math.sqrt(5)
return round(result)
# Test Binet's formula
print("Binet's Formula Results:")
for i in range(15):
print(f'F({i}) = {fibonacci_binet(i)}')
# Compare accuracy with iterative method
print("\nAccuracy comparison (Binet vs Iterative):")
for i in [20, 30, 40, 50]:
binet_result = fibonacci_binet(i)
iterative_result = fibonacci_iterative(i)
match = "✓" if binet_result == iterative_result else "✗"
print(f'F({i}): Binet={binet_result}, Iterative={iterative_result} {match}')Challenge Yourself
Performance Comparison Challenge
Now that you’ve seen all three methods, let’s compare their performance! Try running this timing comparison to see the dramatic differences between approaches:
Challenge Code:
import time
# Time comparison for different methods
def time_function(func, n):
start = time.time()
result = func(n)
end = time.time()
return result, end - start
# Test with a moderate number (careful with recursive!)
test_n = 30
print(f"Computing F({test_n}) with different methods:\n")
# Iterative (fast)
result, duration = time_function(fibonacci_iterative, test_n)
print(f"Iterative: {result} (took {duration:.6f} seconds)")
# Binet's formula (very fast)
result, duration = time_function(fibonacci_binet, test_n)
print(f"Binet's: {result} (took {duration:.6f} seconds)")
# Recursive (slow - be patient!)
print("\nRecursive method running... (this will take a while)")
result, duration = time_function(fibonacci_recursive, test_n)
print(f"Recursive: {result} (took {duration:.6f} seconds)")
print("\n🎯 Challenge: Try changing test_n to see how each method scales!")
print(" - Iterative & Binet's can handle n=50+ easily")
print(" - Recursive becomes very slow after n=35")Your Turn!
Challenge Tasks:
- Modify the recursive function to use memoization (caching previous results) to make it faster
- Create a function that generates the first n Fibonacci numbers using your preferred method
- Investigate the golden ratio - calculate φ (phi) from consecutive Fibonacci numbers: F(n+1)/F(n)
- Research question: Why does Binet’s formula eventually become inaccurate for very large numbers?
Use any of the terminals above to experiment with these challenges!
Summary
In this lesson, you explored three different approaches to computing Fibonacci numbers:
- Recursive Implementation: Elegant but exponentially slow (O(2^n)) - demonstrates the mathematical definition directly
- Iterative Implementation: Efficient and practical (O(n) time, O(1) space) - builds solutions step-by-step
- Binet’s Formula: Mathematically beautiful (O(1) but limited by precision) - uses the golden ratio for direct calculation
- Performance Analysis: Understanding how algorithm choice dramatically affects execution time
Key Takeaways
Each approach teaches us different programming and mathematical concepts: - Recursion and why it can be inefficient without optimization (memoization) - Iteration and the power of building solutions incrementally - Mathematical formulas and their computational trade-offs between elegance and precision - Algorithm complexity and how it affects real-world performance
The Fibonacci sequence appears everywhere in nature and mathematics, making it a perfect example for understanding both algorithmic thinking and mathematical beauty in programming!