Fibonacci Series in Python Using Recursion

Filed Under: Python

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

python recursion, python fibonacci example

We see that,

  • 1st Fibonacci number = 0 (by assumption)
  • 2nd Fibonacci number = 1 (by assumption)
  • 3rd Fibonacci number = 1st + 2nd
    = 0 + 1
    = 1
  • 4th Fibonacci number = 2nd + 3rd
    = 1 + 1
    = 2
  • 5th Fibonacci number = 3rd + 4th
    = 1 + 2
    = 3
  • 6th Fibonacci number = 4th + 5th
    = 2 + 3
    = 5
  • So, nth Fibonacci number = (n-1)th Fibonacci + (n-2)th Fibonacci

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.

python recursion, python fibonacci example

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.

Comments

  1. sai saranya says:

    could you explain with some more examples and also compare it with normal loop .

  2. anonymous says:

    The image is probably wrong. Fibonacci(1) = 0 and Fibonacci(2) = 1 as per the code. But that’s not what’s shown in the image.

    1. Pankaj says:

      It’s just a matter of how you use indexes. Some start at 0 whereas some languages start at 1. The main point is that the series should be 0,1,1,2,3 and so on.

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content