Python Program to Print the Fibonacci Series

Last Updated on November 25, 2022 by Prepbytes

In this article, we will discuss the Fibonacci series in Python. We will discuss the meaning of the Fibonacci series, the Fibonacci Series program in python using iteration, and the Fibonacci series in Python using recursion. So, let’s start first by understanding the meaning of the Fibonacci series.

What is the Fibonacci Series?

The Fibonacci Series is a special series in mathematics. The first two terms of the series are fixed. The index of the first term is 0 and the index of the second term is 1. So, we say that the 0th Fibonacci term is F0 = 0 and the 1st Fibonacci term is F1 = 1.

Now, the rest all the terms are the sum of the previous 2 terms. So, F2 = F0 + F1 = 0 + 1 = 1. Similarly, the next term i.e. F3 = F2 + F1 = 1 + 1 = 2. This behavior continues throughout as shown below.

So, in general, we can say that the following relation holds for all the Fibonacci terms after 1st term:

So, now that we know the concept of the Fibonacci series, let us understand the how to print the Fibonacci series in Python till N terms.

How to Print Fibonacci Series in Python till N Terms

We will be given an integer N. This integer will denote the number of terms in the Fibonacci series. We have to print the Fibonacci Series till Nth term. For instance, let us say that N = 10. So, the output will be as shown below.

We just have to print the sequence i.e. 0 1 1 2 3 5 8 13 21 34 55.

Python Program to Print the Fibonacci series

Using Dynamic Programming

So, we have understood the relation between the Fibonacci terms i.e. the Nth term is the sum of (N-1)th and (N-2)th terms. So, we can use this relation to print the Fibonacci series.

Let us take a list as shown below.

So, the list “dp” has 2 terms 0 and 1. These are the first 2 terms of the Fibonacci series. Also, the terms of the Fibonacci series start from 0. So, we have the 0th and 1st terms already in the list.

Now, to calculate the second term, we will take out the last 2 values from the list and add them. In Python, we can use negative indexing to get the last 2 values of the list as shown below.

So, we will iterate till we are able to fill the list with N Fibonacci terms. So, let’s say that N = 5.

Let us now calculate Fib3 = Fib2 + Fib1 = 1 + 1 = 2. This is shown below.

Next, we calculate Fib4 = Fib3 + Fib2 = 2 + 1 = 3. This is shown below.

Now, at last, we will calculate Fib5 = Fib4 + Fib3 = 3 + 2 = 5. This is shown below.

Finally, we have the list dp as shown below.

So, we have all the N terms of the Fibonacci series stored in the list. For printing the Fibonacci Series to N terms, we simply iterate over this list and print all the elements.

Now that we know the complete procedure, let us write the code for the same.

Fibonacci Series Program in Python using Dynamic Programming

N = int(input())
dp = [0,1]

for i in range(N-1):
    dp.append(dp[-1] + dp[-2])

for i in dp:
    print(i," ",end="")

Time Complexity: The time complexity of this algorithm is O(N) where N is the number of terms of the Fibonacci series that we have to print. This is because we traverse till we find the Nth term.

Space Complexity (Auxiliary Space): Since we used the dp array to store the terms of the Fibonacci series, we can say that the auxiliary space or extra space used is O(N).

So, can we improve this algorithm in terms of time or space? Well, it seems difficult to optimize the algorithm in terms of time because we have to traverse N terms to get the Nth Fibonacci term. However, we can optimize the space complexity of this algorithm. Let us see how.

Python Program to Print the Fibonacci series

Using Space-Optimized Method

Again, the same relation between the terms of the Fibonacci series will be used to solve the problem. However, we can optimize the space.

The idea for optimization is pretty simple. If you notice, in the previous method, we stored all the terms of the Fibonacci series and then printed the entire series in one go. However, we don’t need t store all the terms. This is because the Nth term depends upon only the last 2 terms. So, even if we have just stored the last 2 terms, we can calculate the next term.

So, let us say that N = 5. Now, we know that the first 2 terms of the Fibonacci series are 0 and 1. So, we have already printed them as shown below.

As shown above, we have three variables. The variable first stores 0 and the variable second stores 1 initially as these are the first 2 terms of the Fibonacci series. The variable current = 0 and we have already printed 0 and 1.

Now, we start with the second term i.e. N = 2. So, we know that it will be the sum of the previous 2 terms. So, current = first + second = 0 + 1 = 1. Also, we will print the current i.e. add it to the output too.

Now, we know that the term we just calculated i.e. current, will act as the previous element for the upcoming term. Also, the term previous to current will now become (N-2)th term for the upcoming element. So, we will store them in the variables first and second as shown below.

Now, we will calculate the next term i.e. N = 3. For N = 3, the first and second are as shown below.

Now, we will calculate the current and add it to the output as shown below.

Now, we will change the values of the first and second again as shown below.

Now, we will again solve for N = 4. For N = 4, the values of the first and second are as shown below.

Again, let’s calculate the current and print it as shown below.

Again, the values of the first and second will be changed.

Finally, we will calculate N = 5. All the calculations for N = 5 are shown below.

Finally, we have the output as shown below.

So, we have printed all the Fibonacci terms. Now that we have understood the procedure, let us write the code for the same.

Fibonacci Series Program in Python Using DP – Space Optimization

N = int(input())

a = 0
b = 1
c = 0

if N < 0:
    print("Invalid input")
elif N == 0:
    print("0")
elif N == 1:
    print("0 1")
else:
    print("0  1  ",end="")
    for i in range(N-1):
        c = a + b
        print(c," ",end="")
        a = b
        b = c

Time Complexity: The time complexity of this approach is also O(N). This is because we are traversing till N terms.

Space Complexity (Auxiliary Space): The auxiliary space here is O(1) as we have not used an array or a list. We have just used 2 variables hence the extra space is constant i.e. O(1).

So, we have understood both methods to print the Fibonacci Series in Python. Now, let us understand how to calculate the Nth Fibonacci term using recursion.

Fibonacci Series in Python using Recursion

So, we used the relation between the Fibonacci terms to print the Fibonacci series in the above 2 methods. The same relation can be used to find the Nth term of the Fibonacci series using recursion.

Consider N = 5. This means that we have to find the 5th Fibonacci term. So, the relation FN = FN-1 + FN-2 can be used to achieve this recursively as shown below.

So, as shown in the tree above, F5 calls F4 and F3. Then F3 and F2 and this goes on. However, when the calls are made to either F1 or F0, we stop. This is because these are the base cases as F1 and F0 are the first 2 terms and they are known to us.

So, we will use the same method as shown by the recursion tree above to solve the Fibonacci series in Python using Recursion.

Let us now write the code.

Program for Fibonacci Series in Python Using Recursion

N = int(input())

def fib(N):
    if N == 0 or N == 1:
        return N
    elif N < 0:
        return -1
    else:
        return fib(N-1) + fib(N-2)


res = fib(N)
if res == -1:
    print("Invalid input")
else:
    print(res)

Time Complexity: The time complexity for this approach is O(2N) as at every node of the recursion tree of height N, 2 calls are being made.

Space Complexity (Recursion Space): Since the height of the recursion tree is O(N), the recursion call stack space is O(N).

So, we have now understood the Fibonacci series in Python using iteration and also the Fibonacci series in Python (finding Nth term) using recursion. We hope that you have understood the complete concept and the programs.

Hope to see you again at PrepBytes.