Recursion is one of the most intuitive ways of solving a problem. Basically, to apply dynamic programming techniques in any problem-solving approach, recursion has to be known. Without knowing and understanding recursion, one simply can't get the solution for any dynamic programming problem. To understand recursion well, one needs to know how it works underhood.
In this tutorial, I am going to give a very basic example that everybody gives while teaching how recursion works. But what I am going to do differently is I am going to explain line by line what is happening behind the scene so that beginners can grasp the topic easily. I was pulling my hairs out when at first I was trying to figure out how recursion works, I really could not find any good article which explains it simply. All they did was give a picture of a tree and telling this function is doing this and that. Well, I will do that too but in a different way. So enough with this talking. Let's begin.
A function calling itself is simply called recursion. So let's take an example of recursion using the infamous Fibonacci number series :
Okay, that’s a lot to grasp when you look at the code above. Don’t worry if you don't get it cause we’re going to go line by line. So basically Fibonacci number series works in such a way that we show the next number by adding the previous two numbers. The first two numbers in the Fibonacci series are 0 and 1. So in this case we are going to console out 8 as it is the 6th Fibonacci number. eg: 0 1 1 2 3 5 8.We start counting from 0 here. Anybody who’s having a hard time to grasp what is Fibonacci series can go to this article below,
The Fibonacci Sequence is the series of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... The next number is found by…
Whenever we write a recursive function (meaning a function that calls itself) we have to specify a condition in the function which is called base condition to make the function reach its end or quit whenever the condition is satisfied. If the base condition is not applied then the function will keep on executing until the memory consumption is full which is something that you definitely don't want. Now to define the base condition is a little bit tricky. We have to think in a top-down approach meaning 100 to 1 instead of 1 to 100. So in this example, we quit from the function whenever the value of n is either 0 or 1. So for our example, our base condition is whenever the value of n is 0 or 1 we will quit from the function. So what it means is, we go from 6 to 1. Each time the function calls itself, a new stack is defined in the memory. Now here comes the main part where we demystify this whole thing. So this is happening behind the scene. Check it out:
At the first call, the value of n is 6. So the following will happen in the background,
fib(6–1) + fib(6–2);
See it carefully, the second function call fib(6–2) does not get executed immediately. The code will only start executing it when the first one fib(6–1) returns and stack comes down to it. Stack works in last in first out. So fib(6–2) will be executed in the end. Anyway, we move to our second call.
At the second call, the value of n is 5. So we can write,
As before, fib(5–2) gets stored in the memory for future execution only when its previous part fib(5–1) gets returned(I may repeat a few stuff but my intention is to only make you understand). Alright, so now at the third call,
fib(4–1) + fib(4–2); Similarly this process will keep going until it reaches the base condition. Then at the fourth call,
fib(3–1)+fib(3–2); Then the fifth call, fib(2–1) + fib(2–2); Now in the next call the value of n is going to be 1 which is our base condition. So what to return? We return n which is 1.So 1 is returned from the function call fib(2–1). So now as the previous part is completed, this will move to the next part which is fib(2–2). So remember how the stack works; last in first out. So now memory is pointing to this function call,
So fib (2–2) starts executing and the value of n becomes 0. So it hits the base condition and it returns 0. So the whole function call becomes,
1+0 //which is 1
//fib(2-1) + fib(2-2) is returning 1 to fib(3-1)
so fib(2–1) + fib(2–2) returns 1. At this point, this portion is removed from the stack and we go to the previous part which was fib(3–1). Basically, for fib(3–1) we got 1 as the returned value. So just like before, the next part will start executing which is fib(3–2). I hope that now you’ve started to observe the pattern of function calling and returning. If you don’t then please read it again. In the end, I will give the tree which will make much more sense then. So at this point, we have,
So fib(3–2) will start executing and the total value of it will be returning the value of fib(4–1). So fib(3–2) will return 1. So ultimately fib(4–1)
returns 1+1 =2 . So now we have,
So fib(4–2) will start executing. And now what? The same process again. For fib(4–2) the value of n is 2.
fib(4-2)// value of n is 2
//in the next call,
fib(2-1) + fib(2-2)// 1 + 0 = 1 which is returning value of fib(4-2)
So the function call fib(2–1) + fib(2–2) will ultimately return 1+ 0 = 1 . So fib(4–2) returns 1. So fib(4–1) + fib(4–2) returns 2+1 =3 which is the return value of fib(5–1). Again we’ll go for executing fib(5–2) which will ultimately return 3. It can be explained through this picture:
So fib(5–1) + fib(5–2) is 3 + 2 = 5 which is the return value of fib(6–1) and for our last call fib(6–2) we do the same process again. I won't show this last one. I leave it up for you because it is similar to the ones we have done so far and I believe if you have understood so far you will be able to do it on your own. So fib(6–2) will ultimately return 3. So fib(6-–1) + fib(6–2) finally returns 5+ 3 =8 which is our result and the 6th number of Fibonacci series (counting starts from 0). Wow! a lot of things indeed happening behind the scene. As you can understand, this process will become very large. The time complexity of this approach is O(2^n) which is exponential and something that you want to improve. That’s why for reducing the time complexity of this process we use dynamic programming which is out of the scope of this article. Maybe some other time. So if you have come this far, thanks for having the patience to read it. I hope it clears out your confusion regarding recursion. Now, in the end, I will put the final recursive tree structure of the whole operation we have done so far which I believe you will understand easily if you have read this article from the beginning. Good luck!