Recursive code to compute the nth Fibonacci number.

Recursion:

“Recursion is a process in which a problem is defined in terms of itself”.

The problem is solved by repetitively breaking it into a smaller problem which is similar in nature to the original problem.

To compute nth Fibonacci number using recursion the below code helps:

# Function for nth Fibonacci number 
 
def Fibonacci(n): 
 if n<0: 
   print(“Incorrect input”) 
 # First Fibonacci number is 0 
 elif n==1: 
   return 0
 # Second Fibonacci number is 1 
 elif n==2: 
   return 1
 else: 
   return Fibonacci(n-1)+Fibonacci(n-2) 
 
# Driver Program 
 
print(Fibonacci(6))# Function for nth Fibonacci number 
 

To compute the Fibonacci number of 6 th position,code does the following process:

Fibonacci(6) returns Fibonacci(5)+Fibonacci(4)

fibonacci(5)+Fibonacci(4) returns fibonacci(4)+Fibonacci(3)+Fibonacci(3)+Fibonacci(2)

[Fibonacci(2) will be return 1 and Fibonacci(1) returns 0]

Recursively, fibonacci(3)+Fibonacci(2)+Fibonacci(2)+Fibonacci(1)+Fibonacci(2)+ Fibnacci(1)+1

Again recursively, Fibonacci(2)+Fibonacci(1)+1+1+0+1+0+1

Finally, 1+0+1+1+0+1+0+1=5

5 will be printed on the console