How to Write the Fibonacci Sequence in Python

Introduction

The Fibonacci sequence is a fascinating mathematical series where each number is the sum of the two preceding ones. Let’s explore different ways to implement this sequence in Python, comparing their efficiency and use cases.

The Fibonacci sequence starts with 0 and 1. Each subsequent number is the sum of the previous two numbers, forming a sequence like this:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

The Fibonacci sequence can be defined mathematically as:

\[ F(n) = F(n-1) + F(n-2), \quad \text{where:} \]

\[ F(0) = 0 \quad \text{and} \quad F(1) = 1 \]

1. Recursive Implementation

One of the simplest and most intuitive ways to calculate the Fibonacci sequence is through recursion. In this approach, the function calls itself with smaller values of n until it reaches the base cases (0 and 1). Here’s the code:

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

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

2. Dynamic Programming Approach

The recursive approach is elegant but inefficient for larger values of n due to its exponential time complexity. We can significantly improve performance using dynamic programming by storing intermediate results (memoization). This reduces redundant calculations and improves time complexity to O(n).

def fibonacci_dp(n):
    if n <= 1:
        return n

    dp = [0] * (n + 1)
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[n]

# Usage
print([fibonacci_dp(i) for i in range(10)])
# Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

3. Space-Optimized Iterative Solution

The dynamic programming approach is efficient in terms of time complexity but can still be optimized for space. Instead of storing the entire sequence, we can calculate Fibonacci numbers using only two variables. This reduces the space complexity from O(n) to O(1).

def fibonacci_iterative(n):
    if n <= 1:
        return n

    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# Usage
print([fibonacci_iterative(i) for i in range(10)])
# Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

4. Generator Implementation

When working with large Fibonacci sequences, storing all values in memory can become impractical. Instead, we can use a generator to produce Fibonacci numbers on demand. This approach leverages Python's yield keyword to create an efficient, memory-friendly implementation.

def fibonacci_generator():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

# Usage
fib = fibonacci_generator()
first_10 = [next(fib) for _ in range(10)]
print(first_10)
# Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

5. Class-Based Implementation

A class-based implementation provides a structured way to encapsulate the logic of generating Fibonacci numbers. By implementing the iterator protocol, we can create an iterable Fibonacci sequence with a defined maximum length.

class FibonacciSequence:
    def __init__(self, max_length):
        self.max_length = max_length

    def __iter__(self):
        self.n1 = 0
        self.n2 = 1
        self.count = 0
        return self

    def __next__(self):
        if self.count >= self.max_length:
            raise StopIteration

        if self.count == 0:
            self.count += 1
            return self.n1
        elif self.count == 1:
            self.count += 1
            return self.n2

        result = self.n1 + self.n2
        self.n1 = self.n2
        self.n2 = result
        self.count += 1
        return result

# Usage
fib_sequence = FibonacciSequence(10)
print(list(fib_sequence))
# Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Performance Comparison

Understanding the performance differences between various Fibonacci implementations is crucial for selecting the most efficient approach for a given use case. Below is a simple benchmark script to compare the recursive, dynamic programming, and iterative implementations.

import time

def benchmark(func, n):
    start = time.time()
    result = func(n)
    end = time.time()
    return end - start

n = 35
print(f"Recursive: {benchmark(fibonacci_recursive, n):.9f} seconds")
print(f"Dynamic Programming: {benchmark(fibonacci_dp, n):.9f} seconds")
print(f"Iterative: {benchmark(fibonacci_iterative, n):.9f} seconds")

Benchmark Results

Below are the benchmark results for calculating F(35) using different implementations of the Fibonacci sequence:

Practical Applications

The Fibonacci sequence has numerous real-world applications, from approximating mathematical constants like the Golden Ratio to analyzing properties of the sequence itself. Below are two practical examples demonstrating its utility.

def calculate_golden_ratio(n):
    fib = fibonacci_iterative(n)
    prev_fib = fibonacci_iterative(n-1)
    return fib / prev_fib

# As n increases, this ratio approaches the golden ratio (≈ 1.618034)
print(calculate_golden_ratio(100))

def analyze_sequence(n):
    sequence = [fibonacci_iterative(i) for i in range(n)]
    even_sum = sum(x for x in sequence if x % 2 == 0)
    odd_sum = sum(x for x in sequence if x % 2 != 0)
    return {
        'sequence': sequence,
        'even_sum': even_sum,
        'odd_sum': odd_sum,
        'ratio': even_sum / odd_sum if odd_sum != 0 else 0
    }

print(analyze_sequence(10))

Conclusion

Congratulations on reading to the end of this tutorial! You have explored various implementations of the Fibonacci sequence in Python, including iterative, recursive, dynamic programming, generator-based, and class-based approaches. These implementations illustrate key Python programming concepts:

• Recursive vs. Iterative Approaches: Understanding the trade-offs between clarity and performance.
• Dynamic Programming: Optimizing performance by storing intermediate results.
• Generators and Iterators: Using lazy evaluation for memory-efficient solutions.
• Object-Oriented Programming: Creating modular and reusable code with class-based designs.
• Performance Optimization: Benchmarking and choosing the best approach for your specific requirements.

The Fibonacci sequence and Fibonacci numbers are ubiquitous in nature and underpin fascinating mathematical expressions. Learning how to implement the Fibonacci sequence is particularly helpful for understanding how recursion works in Python.

To learn how to implement the Fibonacci sequence in C++, visit the article: How to Write the Fibonacci Sequence in C++.

For further reading on recursive functions, check out the article: How to Find the Factorial of a Number in Python.

If you found this guide helpful, feel free to link back to this post for attribution and share it with others exploring logistic regression in PyTorch!

Have fun and happy researching!

Suf

Senior Advisor, Data Science | [email protected] | + posts

Suf is a senior advisor in data science with deep expertise in Natural Language Processing, Complex Networks, and Anomaly Detection. Formerly a postdoctoral research fellow, he applied advanced physics techniques to tackle real-world, data-heavy industry challenges. Before that, he was a particle physicist at the ATLAS Experiment of the Large Hadron Collider. Now, he’s focused on bringing more fun and curiosity to the world of science and research online.

• Suf

  https://researchdatapod.com/author/soofyserial/

  How to Solve TypeError: Cannot perform 'rand_' with a dtyped [object] array and scalar of type [bool]
• Suf

  https://researchdatapod.com/author/soofyserial/

  How to Solve Python TypeError: can only join an iterable
• Suf

  https://researchdatapod.com/author/soofyserial/

  How to Solve Python ValueError: must have exactly one of create/read/write/append mode
• Suf

  https://researchdatapod.com/author/soofyserial/

  How to Solve Python SyntaxError: ‘break’ outside loop