Python Program to Print the Fibonacci Sequence

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:

F_n = F_n-1 + F_n-2

Where, F_n denotes the nth term of Fibonacci series.

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

• F₀ = 0 (Zeroth term of Fibonacci sequence)
• F₁ = 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:

• F₂ = F₁ + F₀ = 0 + 1 = 1
• F₃ = F₂ + F₁ = 1 + 1 = 2
• F₄ = F₃ + F₂ = 2 + 1 = 3

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

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.

• Fibonacci Series in Python using While Loop
• Fibonacci Series in Python using Recursion
• Print nth Fibonacci Number using Dynamic Programming (Bottom-Up Approach)

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.

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

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.

• 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’.

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

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

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))

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.

• Time Complexity: O(2ⁿ) – The time complexity of this program is exponential, O(2ⁿ), 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’.

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

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.

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)

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.

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”.