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

## What is the Fibonacci Sequence?

The Fibonacci sequence is a common sequence defined as follows:

- fib
_{0}= 0 - fib
_{1}= 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}= 0 and fib_{1}= 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.