Python Print the Fibonacci Sequence

Fibonacci sequence is a series of numbers where a number is the sum of the two previous numbers.

In this tutorial, you will learn how to print the Fibonacci sequence in Python.

There are 3 ways to print the Fibonacci series in Python:

• Use recursion to print the Fibonacci sequence
• Use a loop to print the Fibonacci sequence
• Use the Binet's formula to print the Fibonacci sequence

Contents

• What is the Fibonacci Sequence?
• Use Recursion to Print the Fibonacci Sequence
  • Naive Solution
  • Memoization
• Using a Loop to Print the Fibonacci Sequence
• Using the Binet's Formula to Print the Fibonacci Sequence
• Conclusion

What is the Fibonacci Sequence?

The Fibonacci sequence is a common sequence defined as follows:

• fib₀ = 0
• fib₁ = 1
• fib_n = fib_n-1 + fib_n-2 for n > 1

So the first 10 terms of the Fibonacci series will be 0, 1, 1, 2, 3, 5, 8, 13, 21, 34.

If you want to dive more, you can check this tutorial from MathIsFun.

In the next section, I will show you how to calculate and print the Fibonacci sequence using Python.

Use Recursion to Print the Fibonacci Sequence

As can be seen from its definition, the Fibonacci sequence can be calculated recursively with:

• Base case: fib₀ = 0 and fib₁ = 1
• Recursive case: fib_n = fib_n-1 + fib_n-2 for n > 1

Naive Solution

Let's implement the naive solution based on what we observed:

def fib(n):
    if n == 0: # base case
        return 0
    if n == 1: # base case
        return 1
    return fib(n - 1) + fib(n - 2) # recursive case

Now, we can print the first 10 terms of the Fibonacci sequence:

for i in range(10):
    print(fib(i), end=" ")
 
# 0 1 1 2 3 5 8 13 21 34

This is the most intuitive way to print the Fibonacci sequence. However, it is not efficient because we have to calculate the same values multiple times.

Imagine this, if you want to find fib(5), you have to calculate fib(4) and fib(3). Then, to calculate fib(4), you have to calculate fib(3) and fib(2). And so on.

So fib(3) is calculated twice, fib(2) and fib(1) will be recalculated more and more, which is inefficient.

Let's optimize it by using the memoization technique.

Memoization

In simple words, memoization is a technique to store the results of function calls so that we can reuse them.

In this case, we will have to reuse fib(4), fib(3), fib(2), and so on. So we should store them for later use.

Let's use another list to store the computations:

def fib(n, memo):
    if n == 0: # base case
        return 0
    if n == 1: # base case
        return 1
    if memo[n] == 0: # if not calculated yet
        memo[n] = fib(n - 1, memo) + fib(n - 2, memo) # recursive case
    return memo[n]
 
memo = [0] * 10 # initialize the memo list
for i in range(10):
    print(fib(i, memo), end=" ")
 
# 0 1 1 2 3 5 8 13 21 34

Cool, we got the point.

If you want to see the difference, create a count variable and print it out like this:

def fib(n, memo, count):
    count += 1
    if n == 0: # base case
        return 0
    if n == 1: # base case
        return 1
    if memo[n] == 0: # if not calculated yet
        memo[n] = fib(n - 1, memo, count) + fib(n - 2, memo, count) # recursive case
    return memo[n]
 
memo = [0] * 10 # initialize the memo list
count = 0
for i in range(10):
    print(fib(i, memo, count), end=" ")
print(count)

Just copy and try your self.

Using a Loop to Print the Fibonacci Sequence

A more straightforward way to print the Fibonacci sequence is to use a loop.

fib = [0] * 10 # initialize the list
fib[1] = 1 # set the first term
 
for i in range(2, 10): # loop from 2 to 9
    fib[i] = fib[i - 1] + fib[i - 2] # calculate the next term
 
for i in range(10):
    print(fib[i], end=" ")
 
# 0 1 1 2 3 5 8 13 21 34

This is similar to the previous solution, but we don't have to use recursion.

Using the Binet's Formula to Print the Fibonacci Sequence

The Binet's formula is a formula to calculate the Fibonacci sequence, you can read more on another article about Binet's Formula for n-th Fibonacci.

In the scope of this tutorial, I will just put the code here.

from math import sqrt
 
def fib(n):
    return int(((1 + sqrt(5)) ** n - (1 - sqrt(5)) ** n) / (2 ** n * sqrt(5)))
 
for i in range(10):
    print(fib(i), end=" ")
 
# 0 1 1 2 3 5 8 13 21 34

Conclusion

Cool, let's recap the tutorial.

There are 3 ways to calculate the Fibonacci sequence in Python:

• Using recursion
• Using a loop
• Using the Binet's formula

In my opinion, using a loop is a good choice as its simplicity and efficiency.

You can use the Binet's formula when you need to calculate a large Fibonacci number, but it will get inaccurate when the number is too large.