Generate Fibonacci Sequence in Python

In this short tutorial, you’ll learn multiple ways to generate a Fibonacci sequence in Python and display it using the print() method. But, let’s first quickly understand the background and importance of Fibonacci in mathematics.

The concept of Fibonacci first came into existence in 1202 from a book by an Italian mathematician. The title of the book was “Liber Abaci.” However, similar sequences existed in Indian mathematics before his work. Fibonacci starts with 0 and 1 and then grows by adding every two consecutive numbers. For example, here is a shorter version of the series.

0, 1, 1, 2, 3, 5, 8...

The Fibonacci sequence is important in mathematics because it has many interesting properties and appears in many unexpected places in nature and art. For example, the Fibonacci sequence can be used to:

Modeling the growth of populations
Describing spiral patterns in nature
Creating aesthetically pleasing designs
Developing efficient algorithms for computer science problems

Different Ways to Generate Fibonacci Sequence in Python

There are several ways to generate a Fibonacci sequence in Python. We’ll try to cover most of those methods. Firstly, let’s start with the basic one.

1. Using While Loop

You can use a loop, such as a for or while loop, to generate a Fibonacci sequence by iteratively adding the last two numbers in the sequence to produce the next number. Here’s a sample program using a while loop:

For writing this demo code, you should be familiar with the basics of Python programming. In order to prepare yourself, the following topics could help you:

• Python if else
• Python while loop

We’ll use both of the above constructs to form the Fibonacci sequence in the sample given below. This series is a list of integer numbers as shown here.

The above sequence starts with the two pre-defined numbers 0 and 1. The remaining other values get generated by adding the preceding two digits appearing in the list.

It means if you wish to know the value at the index X, then it would be the sum of values at the (X-1) and (X-2) positions.

In the below program, we are using two numbers X and Y to store the values for the first two elements (0 and 1) of the Fibonacci sequence.

After that, there is a while loop to generate the next elements of the list. It is doing the sum of two preceding items to produce the new one.

There is a swapping operation in the next line to continue the while loop until the last element of the sequence gets printed.

# Python code to generate Fibonacci seq using while loop

# The length of our Fibonacci sequence
length = 10

# The first two values
x = 0
y = 1
iteration = 0

# Condition to check if the length has a valid input
if length <= 0:
   print("Please provide a number greater than zero")
elif length == 1:
   print("This Fibonacci sequence has {} element".format(length), ":")
   print(x)
else:
   print("This Fibonacci sequence has {} elements".format(length), ":")
   while iteration < length:
       print(x, end=', ')
       z = x + y
       # Modify values
       x = y
       y = z
       iteration += 1

There could be three possible outputs of the above code.

The length of the sequence is 0 or less than zero.

Please provide a number greater than zero

The sequence contains a single element.

This Fibonacci sequence has 1 element :
0

The sequence contains multiple elements.

This Fibonacci sequence has 10 elements :
0, 1, 1, 2, 3, 5, 8, 13, 21, 34,

You can further play with the program by supplying different values for the length variable.

2. Using Recursion to Generate Fibonacci Sequence in Python

You can also generate a Fibonacci sequence using a recursive function. Here’s an example:

def fibo_recursive(n):
    if n <= 0:
        return []
    elif n == 1:
        return [0]
    elif n == 2:
        return [0, 1]
    else:
        seq = fibo_recursive(n - 1)
        seq.append(seq[-1] + seq[-2])
        return seq

n = 10  # Change 'n' to the desired size of the seq
result = fibo_recursive(n)
print(result)

3. Using Memoization to Generate Fibonacci Sequence in Python

You can optimize the recursive approach by using memoization to store previously calculated Fibonacci numbers to avoid redundant calculations. This can be more efficient for larger values of n.

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 0:
        return []
    elif n == 1:
        return [0]
    elif n == 2:
        return [0, 1]
    else:
        seq = fib_memo(n - 1, memo)
        seq.append(sequence[-1] + seq[-2])
        memo[n] = seq
        return seq

n = 10  # Change 'n' to the desired size of the seq
result = fib_memo(n)
print(result)

Memoization is an advanced version of recursion optimizing it for speed. It caches the expensive function calls and uses the same instead of recomputing them.

4. Using a Generator Function

You can create a generator function to yield Fibonacci numbers one at a time, which is memory-efficient and can be used in a for loop or with the next() function to generate values on the fly.

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

n = 10  # Change 'n' to the desired size of the seq
result = list(gen_fibo(n))
print(result)

5. Using Matrix Exponentiation

It is a technique that can be used to calculate Fibonacci numbers more efficiently for large values of n. It involves raising a specific matrix to the power of n. Here’s a simplified example of how you can do this:

import numpy as np

def matrix_fibo(n):
    F = np.array([[1, 1], [1, 0]], dtype=object)
    result = np.linalg.matrix_power(F, n)
    return result[0, 1]

n = 10  # Change 'n' to the desired Fibonacci number you want to calculate
result = matrix_fibo(n)
print(result)

6. Using Closed-Form Formula

This method doesn’t require a loop or function, instead, use the following formula.

F(n) = (phi^n - (-phi)^(-n)) / sqrt(5)

In this, phi is the golden ratio, a mathematical constant equal to 1.61803. You can use this formula in your Python code to generate a Fibonacci sequence.

Here’s an example of how you can use this formula:

import math

def fibo_formula(n):
    phi = (1 + math.sqrt(5)) / 2
    return round((math.pow(phi, n) - math.pow(-phi, -n)) / math.sqrt(5))

n = 10  # Change 'n' to the desired Fibonacci number you want to calculate
result = fibo_formula(n)
print(result)

Please note that the last two methods improve efficiency and precision in the case of large Fibonacci numbers. However, the matrix exponentiation method may need extra libraries like NumPy for the calculation.

We hope these multiple ways to generate the Fibonacci sequence will help you write better Python programs. You can choose which method works best for your use case.