Home//

Python Print the Fibonacci Sequence

Python Print the Fibonacci Sequence

Minh Vu

By Minh Vu

Updated Oct 19, 2023

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:

What is the Fibonacci Sequence?

The Fibonacci sequence is a common sequence defined as follows:

  • fib0 = 0
  • fib1 = 1
  • fibn = fibn-1 + fibn-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.

Fibonacci Sequence
Figure: Fibonacci Sequence

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: fib0 = 0 and fib1 = 1
  • Recursive case: fibn = fibn-1 + fibn-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.

Binet's Formula
Figure: Binet's Formula

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.

You can search for other posts at home page.
Minh Vu

Minh Vu

Software Engineer

Hi guys, I'm the author of WiseCode Blog. I mainly work with the Elastic Stack and build AI & Python projects. I also love writing technical articles, hope you guys have good experience reading my blog!