How would you implement Fibonacci sequence generation?

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting from 0 and 1. Here are several methods to generate the Fibonacci sequence:

---

1. Iterative Approach (Efficient)

def fibonacci_iterative(n):
    sequence = []
    a, b = 0, 1
    for _ in range(n):
        sequence.append(a)
        a, b = b, a + b
    return sequence

# Example usage
print(fibonacci_iterative(10))  # Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

---

2. Recursive Approach (Less Efficient for Large n)

def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

# Generate a sequence
n = 10
sequence = [fibonacci_recursive(i) for i in range(n)]
print(sequence)  # Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Note: This approach has exponential time complexity (O(2n)O(2^n)) due to repeated calculations.

---

3. Memoization (Efficient Recursive Approach)

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_memoized(n):
    if n <= 1:
        return n
    return fibonacci_memoized(n - 1) + fibonacci_memoized(n - 2)

# Generate a sequence
n = 10
sequence = [fibonacci_memoized(i) for i in range(n)]
print(sequence)  # Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

---

4. Generator Approach

def fibonacci_generator(n):
    a, b = 0, 1
    for _ in range(n):
        yield a
        a, b = b, a + b

# Example usage
print(list(fibonacci_generator(10)))  # Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

---

5. Matrix Exponentiation (Advanced)

This method uses matrix exponentiation for a logarithmic time complexity solution.

import numpy as np

def fibonacci_matrix(n):
    F = np.matrix([[1, 1], [1, 0]])
    result = (F ** (n - 1))[0, 0]
    return result

# Generate a sequence
n = 10
sequence = [fibonacci_matrix(i) for i in range(1, n + 1)]
print(sequence)  # Output: [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

---

6. Using a Formula (Binet’s Formula)

The Fibonacci number can also be computed using the golden ratio (ϕ\phi): F(n)=ϕn−(1−ϕ)n5F(n) = \frac{\phi^n – (1 – \phi)^n}{\sqrt{5}}

import math

def fibonacci_formula(n):
    phi = (1 + math.sqrt(5)) / 2
    return round((phi**n - (-1/phi)**n) / math.sqrt(5))

# Generate a sequence
n = 10
sequence = [fibonacci_formula(i) for i in range(n)]
print(sequence)  # Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

---

Best Practice

• Use the iterative approach or generator for most practical applications.
• Use memoization for recursive implementations if you need recursion and want to avoid repeated calculations.
• Use matrix exponentiation or Binet’s formula for very large Fibonacci numbers.