Python Program to Find the Fibonacci Series Using Recursion

Don’t miss the chance of Java programs examples with output pdf free download as it is very essential for all beginners to experienced programmers for cracking the interviews.

Fibonacci Sequence:

The Fibonacci Sequence is a series of integers named after the Italian mathematician Fibonacci. It is merely a string of numbers that begins with 0 and 1 and is then followed by the addition of the two numbers before it.

Recursion:

If you’re familiar with Python functions, you’ll know that it’s typical for one function to call another. It is also feasible for a function in Python to call itself! A recursive function calls itself, and the process of using a recursive function is known as recursion.

Although it may appear strange for a function to call itself, many sorts of programming challenges are better stated recursively.

Given a number, the task is to find the Fibonacci sequence till the given number using recursion.

Examples:

Example1:

Input:

given number = 23

Output:

The Fibonacci Sequence till the given number 23  =
Number =  0
Number =  1
Number =  1
Number =  2
Number =  3
Number =  5
Number =  8
Number =  13
Number =  21
Number =  34
Number =  55
Number =  89
Number =  144
Number =  233
Number =  377
Number =  610
Number =  987
Number =  1597
Number =  2584
Number =  4181
Number =  6765
Number =  10946
Number =  17711

Example2:

Input:

given number =13

Output:

Enter some random number = 13
The Fibonacci Sequence till the given number 13 =
Number = 0
Number = 1
Number = 1
Number = 2
Number = 3
Number = 5
Number = 8
Number = 13
Number = 21
Number = 34
Number = 55
Number = 89
Number = 144

Program to Find the Fibonacci Series Using Recursion

Below are the ways to find the Fibonacci Series using the recursive approach in Python:

1)Using Recursion(Static Input)

Approach:

• The user must give the number as static input and store it in a variable.
• Pass the given number as a parameter to the Fibonacci recursive function.
• The base condition is defined as a value that is less than or equal to 1.
• Otherwise, call the function recursively with the argument as the number minus 1 plus the function that was called recursively with the parameter as the number minus 2.
• Use a for loop to return the Fibonacci sequence and return the result and print the result.
• The exit of the program.

Below is the implementation:

# function which finds the fibonacci sequence recursively
def fibonacciRecursion(numb):
# The base condition is defined as a value that is less than or equal to 1.
if(numb <= 1):
return numb
else:
# Otherwise, call the function recursively with the argument as the number minus 1 plus the function that was called
# recursively with the parameter as the number minus 2.
return(fibonacciRecursion(numb-1) + fibonacciRecursion(numb-2))

# The user must give the number as static input and store it in a variable.
numb = 23
print("The Fibonacci Sequence till the given number", numb, ' = ')
# Looping from 1 to given number using for loop
for n in range(numb):
# passing the iterter value as argument to the recursive function fibonacciRecursion
print('Number = ', fibonacciRecursion(n))


Output:

The Fibonacci Sequence till the given number 23  =
Number =  0
Number =  1
Number =  1
Number =  2
Number =  3
Number =  5
Number =  8
Number =  13
Number =  21
Number =  34
Number =  55
Number =  89
Number =  144
Number =  233
Number =  377
Number =  610
Number =  987
Number =  1597
Number =  2584
Number =  4181
Number =  6765
Number =  10946
Number =  17711

In this way, we can print the Fibonacci sequence of the given number using recursion.

2)Using Recursion(User Input)

Approach:

• The user must give the number as user input using the int(input()) function and store it in a variable.
• Pass the given number as a parameter to the Fibonacci recursive function.
• The base condition is defined as a value that is less than or equal to 1.
• Otherwise, call the function recursively with the argument as the number minus 1 plus the function that was called recursively with the parameter as the number minus 2.
• Use a for loop to return the Fibonacci sequence and return the result and print the result.
• The exit of the program.

Below is the implementation of the above approach:

# function which finds the fibonacci sequence recursively
def fibonacciRecursion(numb):
# The base condition is defined as a value that is less than or equal to 1.
if(numb <= 1):
return numb
else:
# Otherwise, call the function recursively with the argument as the number minus 1 plus the function that was called
# recursively with the parameter as the number minus 2.
return(fibonacciRecursion(numb-1) + fibonacciRecursion(numb-2))

# The user must give the number as user input using the
# int(input()) function and store it in a variable.
numb = int(input('Enter some random number = '))
print("The Fibonacci Sequence till the given number", numb, ' = ')
# Looping from 1 to given number using for loop
for n in range(numb):
# passing the iterter value as argument to the recursive function fibonacciRecursion
print('Number = ',fibonacciRecursion(n))


Output:

Enter some random number = 13
The Fibonacci Sequence till the given number 13 =
Number = 0
Number = 1
Number = 1
Number = 2
Number = 3
Number = 5
Number = 8
Number = 13
Number = 21
Number = 34
Number = 55
Number = 89
Number = 144



Explanation:

• The number of terms must be entered by the user and saved in a variable.
• A recursive function takes the number as a parameter.
• The number must be less than or equal to one as a starting point.
• Otherwise, the function is run recursively with the number minus 1 as an input, which is added to the function that is called recursively with the number minus 2.
• The result is returned, and the Fibonacci sequence is printed using a for statement.
• In this way, we can print the Fibonacci sequence of the given number using recursion.

Related Programs: