Python Recursion Fibonacci Example

Filed Under: Python

Good day, learners! In this tutorial we are going to learn about Python Recursion and use it for fibonacci sequence generation. In previous tutorial we discussed about Python Function and Arguments.

Python Recursion

Functions that are implemented using recursion can be implemented using loops. But you have to know the basics of Python Recursion. Basically, when a thing is defined by itself, recursion occurs. You may have heard the name of scripting language PHP. The acronym of PHP is PHP Hypertext Preprocessor. This is an example of recursion. In python, recursion occurs when a function is defined by itself. The structure of a Python recursive function is given below


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)

Python Fibonacci Series

Fibonacci series is basically a sequence. In that sequence, each number is sum of previous two preceding number of that sequence. Initial two number of the series is either 0 and 1 or 1 and 1. We will consider 0 and 1 as 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 something using recursion requires less effort. The code you wrote using recursion will be comparatively smaller than the code that is implemented by loops. Again, code that are written using recursion are easier to understand also.

Disadvantages of Python Recursion

Recursion requires more function call. 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.

Again it takes some time to call a function, if the task of the function is done, the it recall the parent function which also cause some time to re-execute the parent function from the previous state. So, recursive function consumes more time to perform it’s task.

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

So, you shouldn’t implement functions using recursion if it can be implemented without recursion. Recursive functions are not that much efficient comparing to that implementation using loop but easier to implement.

So, that’s all about Python recursion. If you have any query about recursion, please comment below.

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
Search in posts
Search in pages