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.
Table of Contents
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,
- 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 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.
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.