Fibonacci Series in Python Using Recursion

Hello Python enthusiasts, today we’re going to learn more about creating the Fibonacci series in Python using recursion. In the previous tutorial, we discussed Python Function and Arguments.

What is Recursion in Python?

Recursion is a more mathematical approach to programming. Most of what you can perform with recursion can be done with simple Python loops as well. But it is important to get a hang of using recursion as a concept that you may want to use in the future.

When a function returns a value that is passed back to the function for further processing, we call this recursion. To avoid an infinite loop, we make use of conditional statements to break out of the recursion

def recursive_function(arguments):
        #check for the terminating condition
        if breaking_condition == True :
                #Calculate result
                return result

        #perform some operation with the arguments
   
        #call the function itself to perform further operation
        return recursive_function(arguments_for_further_operation)

Implementing Fibonacci Series in Python using Recursion

Fibonacci series is basically a sequence. In that sequence, each number is the sum of the previous two preceding numbers of that sequence. The initial two number of the series is either 0 and 1 or 1 and 1.

We will consider 0 and 1 as the first two numbers in our example. So, the first few number in this series are

We see that,

So, the code for implementing the Fibonacci function is given below.

def Fibonacci( pos ):
        #check for the terminating condition
        if pos <= 1 :
                #Return the value for position 1, here it is 0
                return 0
        if pos == 2:
                #return the value for position 2, here it is 1
                return 1

        #perform some operation with the arguments
        #Calculate the (n-1)th number by calling the function itself
        n_1 = Fibonacci( pos-1 )

        #calculation  the (n-2)th number by calling the function itself again
        n_2 = Fibonacci( pos-2 )

        #calculate the fibo number
        n = n_1 + n_2

        #return the fibo number
        return n

#Here we asking the function to calculate 5th Fibonacci
nth_fibo = Fibonacci( 5 ) 

print (nth_fibo)

The above code will calculate the Fibonacci number using recursion technique. The following image will help you to understand the concept in more effective way. In this picture, the blue boxes are the calls of functions where the terminating conditions is met.

Advantages of Python Recursion

Implementing a function using recursion requires less effort, but better code logic and understanding. The code you wrote using recursion will be comparatively smaller than the code that is implemented by loops.

Disadvantages of Python Recursion

Recursion requires more function calls. Each function call stores some state variable to the program stack. If your code requires too many function calls, it will consumes too much memory. So, there may be some possibilities of causing memory overflow if your code is not that much efficient.

Another major disadavantage is that even though the number of lines occupied by recursive functions are lower, the memory required for each call increases significantly. Each call has to store the function call from the previous return until the last iteration is reached. This is when all the values are calculated at the same time.

Furthermore, debugging a recursive function is more difficult in most of the cases.

So, in my humble opinion, if you have a choice between implementing the fibonacci series in Python with recursion and with loops, go the route of using loops. They’re easier to understand and much more efficient.

Conclusion

That’s all for this tutorial. I hope you’ve learned some interesting new things about recursive functions and implementing the Fibonacci series in Python with them. Feel free to drop in a comment if you have any questions.