Previously we have discussed what recursion is and we have developed some intuition on when to use recursion.
Now let's explore two powerful tools to visualize recursion.
Remember, if you can visualize recursion for a coding interview question, it would be very easy to
code out the solution.
So let's explore these two techniques.
The first technique over here is a recursion tree, and we have already discussed the question where
we had to find n factorial.
All right.
And let's say we are just finding five factorial.
And we have the pseudocode over here.
Let's try to draw the recursion tree for this particular pseudocode.
So initially we are calling the function with the input five.
So let me just write f of five over here.
And once we are inside the body of the function because n is not equal to one it's five.
We will again call the function recursively.
Over here we will call f of n minus one.
Or in this case that would be f of four.
So let's write f of four over here.
And once we are inside the function again for the input four, we would again come over here and we
would be calling f of three.
Right.
So again that's over here.
We would be over here and we would have called F of three.
And in a similar manner again we would be inside the function with n equal to three n is not equal to
one.
So we would come over here again and we would call f of two right.
And again we would come over here n is equal to two.
N is not equal to one.
So we will come over here and we will call f of one.
Okay.
Now when we are inside the function with n as one, because n is equal to one, we have reached the
base or terminating condition and therefore we would return one.
So this call over here will return one.
So over here when we called f of two we had to multiply this with n which in this case is two right.
So f of two will return this over here which is one into n which is two.
In that case so f of two will return two into one okay.
And similarly f of three f of three called f of two.
That's this part over here for the call of f of three.
And then you have to multiply it with three.
Right.
So f of three will return two into three.
Okay.
And similarly F of four will return this six over here multiplied with this four.
So that's 24.
And F of five will return this 24 over here multiplied with five which is one, 20 or 24 into five.
So this over here is what we call the recursion tree.
Now this is equal to 120 and we get the answer.
Now you will see that in many questions the recursion tree will look something like this.
You may have multiple branches.
Okay.
So again, we will see that in the course as we go on to future questions.
But I'm just mentioning it over here.
So this also is a typical recursion tree that you will see.
So if you are able to draw the recursion tree for a question then you will see that as we practice more
questions.
If you can do this successfully, you will be easily be able to write the code for the solution.
And this is in fact very helpful to identify the time and space complexity as well.
Now more of that later in the course.
But now let's proceed and take a look at another tool for visualization with respect to recursion,
which is the recursion called stack.
So we have seen the recursion tree.
Now we are exploring the recursion call stack.
So let's again take the same example over here where we wanted to find five factorial.
So how would the recursion call stack look like.
Now before we go ahead and visualize this, remember when a function is called, the computer allocates
memory because it has to remember things like local variables, function parameters, return addresses,
etc. so when a function is called the computer has to allocate memory.
So this is something that you should know.
Now let's proceed and take a look at the recursion call stack for this question over here.
So initially we are calling f of five.
So there would be f of five over here in the recursion call stack okay.
So memory is allocated over here we have f of five.
And we have seen that f of five calls f of four.
So we have f of four over here.
And at this point notice that f of five has not ended.
That's why it's still over here.
Because notice over here we are returning f of four into n.
So it would not have done the multiplication.
This has gone to f of four.
And only once we get the value of this would the computer be able to do the the multiplication of what
we get over here with n which is five in this case.
So notice f of five has not ended.
The computer has to hold on to it and remember it.
So that's why we retain this over here.
And then we proceed F of four will call f of three.
That's something that we have seen.
And then f of three will call f of two.
And then f of two will call f of one.
Now when we reach f of one we have seen that we have reached the base condition.
So it returns one.
So this returning one over here.
When this happens it returns one.
And we pop out F of one from the recursive call stack.
And again notice over here this follows the leaf principle or last in first out.
Notice that in this call stack f of one was the last one to be added, and it's the first one to be
popped out.
So that's why we call it a recursion call stack, because a stack follows the leaf principle.
Last in first out.
Now again more of that later in the course where we discuss the stack data structure.
But I'm just trying to link the concepts over here.
Now this is the recursion call stack.
Quickly summarizing.
It's called a stack because it follows the leaf or last in first out principle.
And again over here we have seen that when we called f of five it did call f of four.
And at that point f of five was not over.
So the computer had to hold on to it.
So popping out starts only when we start returning.
So over here we have seen F of one was popped out and it returned one.
Now F of two can return because it got the value of f of one and it multiplies that value with two.
So f of two will return one into two.
Okay.
And we can pop out f of two.
Similarly f of three will return two into three and we can pop out f of three.
And similarly f of four will return.
Six into four and we can pop out F of four, and F of five will return 24 into five and we are done.
We can pop out F of five as well, and we get the answer which is 120.
Now this over here is what we call the recursion call stack.
Now the recursion tree and the recursion call stack are very powerful tools.
They are very important because they help us to calculate especially the space complexity.
We'll see that in future questions and in many questions.
It's very helpful to calculate the time complexity as well.
Now when we talk about the recursion call stack over here, we have seen that at max at a point it's
taking up space of the order of n where n in this case is five.
So over here this takes up space of the order of n.
So if we have a call stack that looks like this, this would take space of the order of n which is again
auxiliary space.
It's extra space.
We have understood how to go about visualizing recursion using a recursion tree or recursion call stack.
In the next video, let's discuss the difference between recursion and iteration.