Recursive approach to print Nth Fibonacci Number

In this tutorial, we will learn how to print the Nth Fibonacci number using recursion (recursive program) in Python.

Before starting this tutorial, it is taken into consideration that there is a basic understanding of recursion.

Check: Introduction to Recursive approach using Python

If not, please don’t hesitate to check this link out.

Now we are really good to go. Certainly, let’s understand what is Fibonacci series.

Fibonacci Series:

0 1 1 2 3 5 8 13 21 34 55 . . . . .

It can be concluded that the present value depends on the last two values.

Certainly, from the above series it could be found that,

fib(0) = 0

fib(1) = 1

fib(2) = 1

fib(3) = 2

Therefore it can be said that fib(4) = fib(3) + fib(2)

So, in general, it can be written that, fib(n) = fib(n-1) + fib(n-2)

This is how the recurrence relation is found.

Now it’s time for the base case. It’s just about the beginning point like in this example,

fib(0) and fib(1) are the starting points.

Let’s code it now stepwise.

def fib(n):
    
    if n==0:                 # base case 1
        
        return 0
    
    elif n==1:               # base case 2
        
        return 1
    
    else:                    # recurrence relation
        pass            
    # as of now kept empty
        

Certainly, this is how the base cases are structured and as of now, there is no recurrence relation inside it.

So, the relation we found for this problem should be kept in the else block.

Moreover, it can be considered as Two-dimensional Recursive Program as,

A function calls itself two times in its function definition.

fib(3)----- fib(2) + fib(1)

fib(2)-----fib(1)  + fib(0)

As it can be seen that every function calls itself two times until it reaches the base cases.

Now all set and it’s time to move for the setup of the recurrence relation and the whole code.

def fib(n):
    
    if n==0:                 # base case 1
        
        return 0
    
    elif n==1:               # base case 2
        
        return 1
    
    else:                    # recurrence relation
        return fib(n-1) + fib(n-2) 
        

n = int(input())

val = fib(n)

print ("The",n,"th fibonacci number is",val)
    

Output:

8
The 8th fibonacci number is 21

I hope, this relaxes the critical concept of using recursion as a solution to a problem and how to write any recursive solution in light speed.

In the coming tutorials, there are a lot of complex problems to be solved using our native two-step approach.