📐 The Fibonacci Sequence

Who Was Fibonacci?

Leonardo of Pisa, known as Fibonacci, was a 13th-century Italian mathematician who introduced the Hindu-Arabic numeral system to Europe. His name became immortalized through the Fibonacci sequence, where each number is the sum of the two preceding ones (0, 1, 1, 2, 3, 5, ...). Found in nature, art, and algorithms, it is a beautiful example of mathematics in the wild.

Below, you'll find two sections: the original, simple implementations of the sequence, followed by optimized techniques using memoization, iteration, and tail recursion in various languages.

Implementations

Simple Recursive Versions

🐍 Python (Recursive) 
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(10))  # Output: 55
🟨 JavaScript (Recursive) 
function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(10)); // Output: 55
🧊 C++ (Recursive) 
#include <iostream>

int fibonacci(int n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
  std::cout << fibonacci(10);  // Output: 55
}
🦀 Rust (Recursive) 
fn fibonacci(n: u32) -> u32 {
    if n <= 1 { return n; }
    fibonacci(n - 1) + fibonacci(n - 2)
}

fn main() {
    println!("{}", fibonacci(10));  // Output: 55
}
🔵 C (Recursive) 
#include <stdio.h>

int fibonacci(int n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
  printf("%d\n", fibonacci(10));  // Output: 55
  return 0;
}

Optimized Versions

🐍 Python (Memoization) 
# Memoized version using a cache dictionary
def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

print(fibonacci(30))  # Output: 832040
🟨 JavaScript (Iterative) 
// Iterative version with constant space
function fibonacci(n) {
  if (n <= 1) return n;
  let prev = 0, curr = 1;
  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}

console.log(fibonacci(30)); // Output: 832040
🧊 C++ (Dynamic Programming) 
// Bottom-up approach using vector
#include <iostream>
#include <vector>

int fibonacci(int n) {
  if (n <= 1) return n;
  std::vector<int> dp(n + 1);
  dp[0] = 0; dp[1] = 1;
  for (int i = 2; i <= n; ++i)
    dp[i] = dp[i - 1] + dp[i - 2];
  return dp[n];
}

int main() {
  std::cout << fibonacci(30);  // Output: 832040
}
🦀 Rust (Tail Recursion) 
// Efficient tail-recursive implementation
fn fibonacci(n: u32) -> u32 {
    fn fib_tail(n: u32, a: u32, b: u32) -> u32 {
        if n == 0 { a } else { fib_tail(n - 1, b, a + b) }
    }
    fib_tail(n, 0, 1)
}

fn main() {
    println!("{}", fibonacci(30));  // Output: 832040
}
🔵 C (Iterative) 
// Iterative version using loop
#include <stdio.h>

int fibonacci(int n) {
  if (n <= 1) return n;
  int prev = 0, curr = 1, temp;
  for (int i = 2; i <= n; i++) {
    temp = curr;
    curr += prev;
    prev = temp;
  }
  return curr;
}

int main() {
  printf("%d\n", fibonacci(30));  // Output: 832040
  return 0;
}

FAQ

What is the Fibonacci sequence?

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting from 0 and 1.

Where is the Fibonacci sequence used?

It appears in nature (e.g., flower petals, pinecones), art, architecture, and computer algorithms.

How is the Fibonacci sequence related to the Golden Ratio?

The ratio of consecutive Fibonacci numbers approaches the Golden Ratio as the numbers increase.