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.
Table of Contents
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
We see that,
- 1st Fibonacci number = 0 (by assumption)
- 2nd Fibonacci number = 1 (by assumption)
- 3rd Fibonacci number = 1st + 2nd
= 0 + 1
- 4th Fibonacci number = 2nd + 3rd
= 1 + 1
- 5th Fibonacci number = 3rd + 4th
= 1 + 2
- 6th Fibonacci number = 4th + 5th
= 2 + 3
- 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.
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.