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
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.
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.
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
Let's implement the naive solution based on what we observed:
Now, we can print the first 10 terms of the Fibonacci sequence:
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(3). Then, to calculate
fib(4), you have to calculate
fib(2). And so on.
fib(3) is calculated twice,
fib(1) will be recalculated more and more, which is inefficient.
Let's optimize it by using the memoization technique.
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(2), and so on. So we should store them for later use.
Let's use another list to store the computations:
Cool, we got the point.
If you want to see the difference, create a
count variable and print it out like this:
Just copy and try your self.
A more straightforward way to print the Fibonacci sequence is to use a loop.
This is similar to the previous solution, but we don't have to use recursion.
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.
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.