Fibonacci series using recursion
We all have made the program to calculate the sum of the Fibonacci series either in our school or university’s programming class.
But, there has always been a great loophole in the way we write our Fibonacci series. Let’s dive a little deep deeper into the concept and the different moving parts.
Here is the normal code that a programmer would write for Fibonacci using recursion.
Although this may seem completely fine and provide the correct output, at the same time, it suffers from the problem of some unnecessary calls!
So, what is the problem with this code?
If we construct the tree of the total calls made by this function, it looks something like this:
It is pretty clear, there are excessive numbers of calls that are not required at all. The function is being called for 2, 3times, and for 0 and 1, multiple times. This makes the code not so efficient. We have to find some way in which we can eliminate these repetitive calls of the function.
So, what we are going to do is that we will go to google and search for the best approach and then copy-paste the code!
Haaaaaa! Just kidding. My apology for the PJ.
Let’s see a better approach now.
If we make an array and keep storing the result of calls, then we won’t need to make calls for the same integer over and over again.
So, let's make a new array and initialize all the values to -1 for now.
And then, after each function returns back the value, we will store it in the respective array element.
Before making any call further, we will check if we have the value of the function for that particular number already stored in an array. If we have it, we won't make another call, otherwise, we will make the call.
And here is the tree with a better approach.
All the red crosses denote that these calls will not be made as all these function values are already stored in the array arr. This technique of storing function calls, to eliminate repetitive calls is called memoization.
And that is your improved version of the code!
Enjoy Buds!
Here are some of my profiles if you want to connect with this geek!
