Python Program to Print the Fibonacci Sequence

Problem Description

Write a Python program to generate the Fibonacci series.

What is Fibonacci Series in Python?

The Fibonacci series is a sequence of numbers in which each number is the sum of the two preceding ones. In Python, the Fibonacci series can be implemented using a loop or recursion. It starts with 0 and 1, and each subsequent number is the sum of the two previous numbers. For example, the Fibonacci series begins as 0, 1, 1, 2, 3, 5, 8, 13, and so on.

Mathematically, we can denote it as:

Fn = Fn-1 + Fn-2

Where, Fn denotes the nth term of Fibonacci series.

The first two terms of this series are considered to be:

advertisement
advertisement
  • F0 = 0 (Zeroth term of Fibonacci sequence)
  • F1 = 1 (First term of Fibonacci sequence)

Now, by using the above two values we can easily calculate all other terms of Fibonacci series as follows:

  • F2 = F1 + F0 = 0 + 1 = 1
  • F3 = F2 + F1 = 1 + 1 = 2
  • F4 = F3 + F2 = 2 + 1 = 3

The series continues as 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, and so on.

Problem Solution

In the Fibonacci series, the first two numbers are 0 and 1, and each subsequent number is the sum of the previous two.

There are several ways to print the Fibonacci series in Python. Let’s take a detailed look at all the approaches to display the Fibonacci series in Python.

Method 1: Fibonacci Series in Python using While Loop

This method involves generating the Fibonacci series in Python using a while loop. It takes the first two numbers of the series along with the number of terms needed and prints the Fibonacci series.

Program/Source Code

Here is source code of the Python Program to find the fibonacci series using while loop. The program output is also shown below.

# Fibonacci Series in Python using While Loop
 
a=int(input("Enter the first number of the series "))
b=int(input("Enter the second number of the series "))
n=int(input("Enter the number of terms needed "))
print(a,b,end=" ")
while(n-2):
    c=a+b
    a=b
    b=c
    print(c,end=" ")
    n=n-1
Program Explanation

1. The user is required to enter the first two numbers of the series and the number of terms to be printed.
2. The first two terms are printed outside the while loop.
3. A while loop is used to find the sum of the first two terms and proceed the series by interchanging the variables.
4. The value of ‘n’ is decremented.
5. The fibonacci series is printed till n-2 is greater than 0.

advertisement
Time and Space Complexity:
  • Time Complexity: O(n) – The time complexity of this program is O(n) as it iterates ‘n’ times to generate the Fibonacci series.
  • Space Complexity: O(1) – The space complexity is O(1) as it uses a constant amount of space to store the variables ‘a’, ‘b’, ‘c’, and ‘n’.
Runtime Test Cases

Testcase 1: In this case, we enter “4” as the number of terms needed to generate the Fibonacci series.

Enter the first number of the series 0
Enter the second number of the series 1
Enter the number of terms needed 4
0 1 1 2

Testcase 2: In this case, we enter “5” as the number of terms needed to generate the Fibonacci series.

Enter the first number of the series 2
Enter the second number of the series 4
Enter the number of terms needed 5
2 4 6 10 16

advertisement
Method 2: Fibonacci Series in Python using Recursion

In this method, we utilize a Python program to compute the Fibonacci series using recursion up to the specified term.

Program/Source Code

Here is source code of the Python Program to find the fibonacci series using recursion. The program output is also shown below.

# Python Program to find the fibonacci series using recursion
 
def fibonacci(n):
    if(n <= 1):
        return n
    else:
        return(fibonacci(n-1) + fibonacci(n-2))
n = int(input("Enter number of terms:"))
print("Fibonacci sequence:")
for i in range(n):
    print(fibonacci(i))
Program Explanation

1. Take the number of terms from the user and store it in a variable.
2. Pass the number as an argument to a recursive function named fibonacci.
3. Define the base condition as the number to be lesser than or equal to 1.
4. Otherwise call the function recursively with the argument as the number minus 1 added to the function called recursively with the argument as the number minus 2.
5. Use a for loop and print the returned value which is the fibonacci series.
6. Exit.

Complexity Analysis:
  • Time Complexity: O(2n) – The time complexity of this program is exponential, O(2n), as it makes recursive calls to the Fibonacci function for each value from 0 to n.
  • Space Complexity: O(n) – The space complexity is O(n) as the recursive calls consume space on the call stack proportional to the input value ‘n’.
Program Output

In this case, we enter “7” as the number of terms needed to generate the Fibonacci series.

Enter number of terms:7
Fibonacci sequence:
0 1 1 2 3 5 8

Method 3: Print nth Fibonacci Number using Dynamic Programming (Bottom-Up Approach)

In this method, Fibonacci numbers are defined by the sequence f(0) = 0, f(1) = 1, and f(n) = f(n – 1) + f(n – 2) for n >= 2. The program prompts the user to enter ‘n’ and prints the nth Fibonacci number.

Program/Source Code

Here is the source code of a Python program to print the nth Fibonacci number using dynamic programming with bottom-up approach. The program output is shown below.

def fibonacci(n):
    """Return the nth Fibonacci number."""
    if n == 0:
        return 0
 
    # r[i] will contain the ith Fibonacci number
    r = [-1]*(n + 1)
    r[0] = 0
    r[1] = 1
 
    for i in range(2, n + 1):
        r[i] = r[i - 1] + r[i - 2]
 
    return r[n]
 
 
n = int(input('Enter n: '))
 
ans = fibonacci(n)
print('The nth Fibonacci number:', ans)
Program Explanation

1. The function fibonacci is defined.
2. fibonacci takes a number n and returns the nth Fibonacci number.
3. It creates a list r where r[n] will contain the nth Fibonacci number.
4. r[0] and r[1] are first initialized to 0 and 1 respectively.
5. The function then fills r by using the formula r[i] = r[i – 1] + r[i – 2].
6. The nth Fibonacci number is then returned.

Time Complexity: O(n)
The time complexity of this program is O(n) as it uses a loop to calculate Fibonacci numbers up to the nth term.

Space Complexity: O(n)
The space complexity is also O(n) as it stores the Fibonacci numbers in a list of size n+1.

Runtime Test Cases

Testcase 1: In this case, we enter the value of n as “7” to find the nth Fibonacci number.

Enter n: 7
The nth Fibonacci number: 13

Testcase 2: In this case, we enter the value of n as “1” to find the nth Fibonacci number.

Enter n: 1
The nth Fibonacci number: 1

Testcase 3: In this case, we enter the value of n as “3” to find the nth Fibonacci number.

Enter n: 3
The nth Fibonacci number: 2

To practice programs on every topic in Python, please visit “Programming Examples in Python”.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.