Three Ways to Generate the Fibonacci Sequence in Python

The Fibonacci Sequence is a famous number sequence. Each number in the Fibonacci sequence is the sum of the two numbers before it. Today, we are going to program 3 ways to generate the Fibonacci Sequence in Python

The sequence, like Python and almost every other programming language, is 0 indexed with the 0th number being 0. The first number is 1. The first and 0th numbers are the “seed” numbers of the Fibonacci sequence. That means that they are the only ones that are set and every other number can be generated from them. The first 11 Fibonacci numbers (starting at 0) are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

In this post we will cover:

• Examples of the Fibonacci Sequence
• Iteratively Generating the Fibonacci Sequence in Python
• Recursively Generating the Fibonacci Sequence in Python

Examples of the Fibonacci Sequence

It shows up in many real life examples. For example, Indian mathematicians first noted it showing up in Sanskrit poems. The below image is taken from Wikipedia showing the pattern of syllable enunciation in Sanskrit poems. It illustrates that there are 13 (the 7th Fibonacci number) ways to arrange long and short syllables in a cadence of 6. Of these 13, 5 (the 5th Fibonacci number) end with a short syllable, and 8 (the 6th Fibonacci number) end with a long syllable.

Another application of the Fibonacci sequence is as an approximation of the Golden Ratio. The below image shows an approximation of the golden spiral generated using Fibonacci numbers. The golden spiral is a self-similar (looks the same as you zoom in and out) spiral with a growth ratio of the golden ratio. Examples of the golden spiral in nature are spiral galaxies and the arrangement of leaves on a plant stem.

There are at least three ways to generate the Fibonacci sequence, here we will cover three of them. You can generate Fibonacci numbers iteratively, recursively, or with dynamic programming. We won’t need any non-native Python libraries so we won’t need to install anything extra through the command line. Let’s get into how we can generate the Fibonacci sequence in Python

Iteratively Generating the Fibonacci Sequence in Python

What does it mean to do something iteratively? It means we’re going to apply a repeated rule a set number of times. In this case, the repeated rule we’re applying is that a Fibonacci number is the sum of the two Fibonacci numbers before it. We have to start with the axiomatic 0th and 1st Fibonacci numbers and return those as 0 and 1 before we get into the iterative generation of the sequence.

To generate the sequence, we seed the sequence with our 0th and 1st Fibonacci numbers. Then loop through n-1 iterations where each iteration sees us adding the last two Fibonacci numbers together to generate the nth one. After we set the value of the nth Fibonacci number we go back and reset the value of the n-1th and n-2th numbers to what they should be. At the end, we return the expected Fibonacci number.

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    f0 = 0
    f1 = 1
    for i in range(n-1):
        f = f0 + f1
        f0 = f1
        f1 = f
    return f
 
print(fibonacci(10))

Running this code should return 55 as pictured below.

Recursively Generating the Fibonacci Sequence

What is a recursive function? A recursive function is one that calls itself. I briefly touched on this when I wrote about Functions and Classes. The Fibonacci sequence is perfect for a recursive relation. Each number is generated as the sum of the two numbers before it. As we always have to do with Fibonacci sequences, we’ll simply seed the 0th and 1st number and away we go. We don’t have to handle re-assigning any numbers to any variables here because we just call the function on n to get the nth Fibonacci number.

What’s a drawback to this? It’s extremely time consuming at a large value of n. For smaller values it’s fine, and it’s also less code than an iterative function, but at large values we’re in trouble. We would have to calculate each number multiple times. When we calculate the 10th Fibonacci number or the 20th Fibonacci number it’s not too bad because the number of wasted calculations grows exponentially. So, how can we solve this? Dynamic Programming. The third approach.

# 0 1 1 2 3 5 8 13 21 ...
def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)
 
print(fibonacci(10))

When we print our 10th Fibonacci number via the recursive function, it should still be 55 like the image below.

Dynamic Programming for the Fibonacci Sequence in Python

Dynamic Programming is an algorithmic technique for solving problems that build upon smaller problems. It is neither dynamic nor does it require programming. Confused? Yeah, me too. I have no idea why they called it that. There are multiple approaches to using dynamic programming to generate Fibonacci numbers but in this case, we’re going to be using the “bottom up” approach. 

A bottom up dynamic programming approach to generating Fibonacci numbers means we’ll be adding the numbers we’ve already calculated to a table so we don’t have to calculate them again. Dynamic programming still uses a recursive approach. Having a table with all the former Fibonacci numbers saves us from an exponential run time.

To do this dynamic programming approach, we start by declaring a table with impossible values. The main advantage of this comes at larger values of n or when we want to generate many Fibonacci numbers. Note that this only works for the positive Fibonacci numbers.

In our fibonacci function, we will start with our axiomatic 0th and 1st numbers as usual. We will add these Fibonacci numbers to our table before we return them. If n is not 0 or 1 we check if it’s already in the table. If it is, then we return the tabulated value, otherwise we’ll use the recursive approach to compute it.

table = [-1 for _ in range(20)]
 
def fibonacci(n):
    if n == 0:
        table[0] = 0
        return 0
    if n == 1:
        table[0] = 0
        table[1] = 1
        return 1
    if table[n] != -1:
        return table[n]
    table[n] = fibonacci(n-1) + fibonacci(n-2)
    return table[n]
 
for i in range(20):
    print(fibonacci(i))

For this example, I’ve decided to use the dynamic programming approach to Fibonacci numbers to generate the first 20. As I said above, one of the advantages of this approach is that it’s nice when you’re generating a lot of numbers as well as for high values of n.

More by the Author

• How to use Python Dotenv
• Prims Algorithm in Python
• Dijkstras Algorithm in Python
• Neural Network Code in Python from Scratch
• Python Generate a Deck of Cards

I run this site to help you and others like you find cool projects and practice software skills. If this is helpful for you and you enjoy your ad free site, please help fund this site by donating below! If you can’t donate right now, please think of us next time.