Fibonacci Series in Python using Recursion

Previously we developed the Fibonacci series program in Python using iteration (for loop, while loop). Now in this post, we will develop the Fibonacci series program using the recursion technique in the Python programming language.

In the Fibonacci series, the next element is the sum of the previous two elements. The Fibonacci sequence is a series of numbers where a number is found by adding up the two numbers before it.

Starting with 0 and 1, the sequence goes 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so forth. As a rule, the expression is Xn= Xn-1+ Xn-2

It is named after an Italian mathematician, Leonardo Fibonacci, who lived in the early thirteenth century. Fibonacci numbers are a series in which each number is the sum of the previous two numbers.

By definition, the first two numbers in the Fibonacci sequence are either 1 and 1, or 0 and 1, depending on the chosen starting point of the sequence, and each subsequent number is the sum of the previous two.

The base case for finding factorial
fibonacci(0) = 0
fibonacci(1) = 1

General case for finding factorial
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)

Fibonacci Series in Python

We can also use the recursion technique to print Fibonacci series in Python. A technique of defining the method/function that contains a call to itself is called recursion. The recursive function/method allows us to divide the complex problem into identical single simple cases that can handle easily. This is also a well-known computer programming technique: divide and conquer.

# Python program to print fibonacci series using recursion

def fibSeries(num):  #user-defined function
    if num <= 1:
        return num
    else:
        return fibSeries(num-1) + fibSeries(num-2)

# take input
num = int(input('Enter number of terms: '))

# print fibonacci series
if num <= 0:
        print('Please enter a positive integer')
else:
    print('The fibonacci series:')
    for i in range(num):
        print(fibSeries(i), end=' ')

Output for the different input values:-

Enter number of terms: 8
The fibonacci series:
0 1 1 2 3 5 8 13

Enter number of terms: 15
The fibonacci series:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377

Find nth Fibonacci Number in Python

# Python program to find n-th fibonacci number using recursion

def fibSeries(num):  #user-defined function
    if num <= 0:
        print('Please enter a positive integer')
    elif num == 1:
        return 0
    elif num == 2:
        return 1
    else:
        return fibSeries(num-1) + fibSeries(num-2)

# take input
num = int(input('Enter number of terms: ')

# print fibonacci term
print('The Fibonacci term is =', fibSeries(num))

Output for the different input values:-

Enter number of terms: 13
The Fibonacci term is = 144

Enter number of terms: 2
The Fibonacci term is = 1

Enter number of terms: 20
The Fibonacci term is = 4181

Also See:- Factorial of a Number in Python using Recursion

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or you find anything incorrect? Let us know in the comments. Thank you!

Leave a Reply