Generating the Fibonacci Sequence in Python

In this post, we’ll explore how to generate the Fibonacci sequence using Python in several ways: iteratively, recursively, and with generators.

Getting Started

The Fibonacci sequence is one of the most well-known sequences in mathematics and computer science. It starts with 0 and 1, and each subsequent number is the sum of the two preceding ones. It starts like this:

 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...(n)  

This sequence appears frequently in algorithms, nature (e.g. spirals of shells, sunflower seed arrangements), and financial markets.

Formally:

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) for n > 1

The Fibonacci sequence is a great example to understand recursion, iteration, and efficient algorithm design. Here's a simple Python implementation of the Fibonacci sequence:

Basic Fibonacci Function Using Loop (Iterative Approach)

def fibonacci(n):  
   sequence = []  
   a, b = 0, 1  
   for _ in range(n):  
     sequence.append(a)  
     a, b = b, a + b  
   return sequence  
 # Example: Print first 10 Fibonacci numbers  
 print(fibonacci(10))  

Output:

 [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]  

Explanation:

• a starts at 0, b at 1 (first two Fibonacci numbers).
• Each loop iteration appends a to the list, then updates a and b to the next values in the sequence.
• This avoids the inefficiency of recursion and works well for large n.

Basic Recursive Approach

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

# Example: Print first 10 Fibonacci numbers
for i in range(10):
    print(fibonacci_recursive(i), end=" ")    

Explanation:

• The function calls itself with n-1 and n-2.
• Base cases:
  • fibonacci(0) returns 0
  • fibonacci(1) returns 1
• All other calls build up from the base cases.

Note:- A more "mathematical" but less efficient approach uses recursion because it is not efficient for large n due to repeated calculations.

Using Memoization (Optimized Recursion)

 from functools import lru_cache  
 @lru_cache(maxsize=None)  
 def fibonacci_memo(n):  
   if n <= 0:  
     return 0  
   elif n == 1:  
     return 1  
   return fibonacci_memo(n-1) + fibonacci_memo(n-2)  
 # Example: Print first 10 Fibonacci numbers  
 for i in range(10):  
   print(fibonacci_memo(i), end=" ")  

Much faster than naive recursion, thanks to memoization.

Using Generators

 def fibonacci_generator():  
   a, b = 0, 1  
   while True:  
     yield a  
     a, b = b, a + b  
 # Example usage: Get first 10 Fibonacci numbers  
 fib_gen = fibonacci_generator()  
 for _ in range(10):  
   print(next(fib_gen), end=' ')  

Explanation:

• yield turns the function into a generator.
• a starts at 0, b at 1 — standard starting values for the Fibonacci sequence.
• Each call to next(fib) returns the next Fibonacci number without recalculating the entire sequence.

Summary

There are many ways to compute the Fibonacci sequence in Python, from simple loops to elegant generators and memoized recursion. Choose the one that best fits your needs—whether it’s readability, performance, or memory efficiency.

Thanks