Everyone.
And welcome back.
So in this video we are going to learn about how to create Recursion Tree for the Fibonacci series.
Now we have earlier created a recursion tree, but that was for a simple problem.
In Fibonacci series.
We have actually made two recursion calls, as we have seen in the last video, and the importance of
recursion tree is that it will be asked to like draw in an interview as well as it helps you to make
your concepts of recursion a lot clearer.
So now let's get started.
First, I'm going to copy the code which we have written in the last class.
So let me go back here.
So this is the code which we have written in the last class.
And based on this actually the recursion tree gets created.
Okay.
So if anyone is asking you to draw the recursion tree, it's always very important that you have the
code or you have the idea, okay, the way in which you are going to write the code.
So you can use the same to draw the recursion tree.
Now let me copy this code as well.
Yep.
Okay.
So this is the code which we have written.
And based on this we are going to make our recursion tree.
Right.
So we have actually called for for let me just start from that only.
Now the next step is actually if we see via code as well, it's that we are calling for last first.
Right.
So we are calling for last.
Okay.
So that's why we are going to draw three.
Now the biggest problem or biggest or biggest mistake which students do is that they draw directly after
this.
They think that the call is going to get made to two.
But that is not what is happening when we are calling for Fibonacci of sorry, Fibonacci of three.
What exactly is going to happen is that another instance of this particular function is going to get
created for three, and that is where the flow of the program will go.
Right.
So on a similar like based on similar thing, we are, what we are going to do exactly is that we are
going to call make the call first for two, but that is going to go from three, right.
So let me remove this as well.
Now this is important because you should be aware that how the calls are going to get made in our function.
Okay.
Based on how you have written it.
If you would have written the second, last first, then we would have made a call to two directly from
four and then to zero directly.
Okay, now this is going to get called for second.
Yeah.
This is going to call to one.
Now one we know is a base case.
One we know is a base case.
So what's exactly going to happen here is that it should return the value as one here.
And along with this I will also write the function calls as well.
Let me use green pen for that.
So this is the very first function call.
This is the second function call.
This is the third one.
This is the fourth one right now once this one is returned from your node of this particular one, which
two call two has the answer for last right?
It is one.
Now it's going to call for zero because it has gotten the answer along with this code.
It has gotten the answer for last.
It's going to call for second last.
And it is going to return with answer one as well.
Since two has now got both the things last and second last, it's going to calculate its answer.
The answer is going to be two.
Right.
And it's going to return that answer to three.
Now three has in a similar way got two as an answer.
And to get the answer for second last it is going to make a call to n minus two which is going to be
one.
Now again this one is a base case.
And I hope you get the idea now that it's going to return with answer one.
So my three node also get both the things that is last and second last.
And the answer is going to be three here which is going to get return.
This answer is going to get returned here which is going to be three.
Now in a similar way we should also write the calls as well.
So this calls is going to be fifth whereas this call is going to be six.
Now I am making everything with a different color pen so that you are able to actually understand that,
which I would say pen denotes what.
So green is actually denoting the number of function calls.
A yellow is denoting the answer, and your orange is denoting what exactly is getting result and what
are the intermediate values which you are getting right.
So now for once, it got the get.
The answer for L is equals to I would say three.
It should now call for n minus two.
So now the finally now the flow will come to the second last line.
And it's going to call for two here.
Now this two again it's not a base case.
So it's going to first make a call to minus one.
Sorry.
First going to make a call to N minus one which is one.
And then it's going to make a call to.
Zero.
Now we are aware that both of these are base cases.
So it is going to they are going to return one and one.
Two is going to get answer L is equals to one and L is equals to one.
Finally going to calculate its answer which is going to be two.
And return this value as well.
So now our fourth the main node has the value of three L and second last last and second last.
Both.
and it is going to return the final answer, which is going to be five.
Now, in this whole flow, the thing which I want all of you to understand is the flow of functions.
Okay, so the one which I am writing from Green Pen and let me show you the same as well.
Okay.
So the way we can see and find the same in code.
Let us just check the same code.
We can maybe define function.
Call number is equals to one.
And in the starting only what?
All we have to do is the function call is.
For.
So I am just writing this code in the starting so that we are able to see for which all the call is
getting made.
So it is just going to help us to actually check our code.
Let me just zoom out a little bit.
Yeah.
It's just going to help us to check our code.
And if I will run it now we are going to see that the first function call is for four.
Okay, next one is for three.
The next one is for two.
So if we see the first one is for four.
Okay.
Next one is for two.
And let me copy this as well so that you are able to see the same thing.
So if we see the calls and this is very important to match.
And make sure that you understand this fully, that if you will see the calls, right, the sequence
of the call that will actually make a lot of things clear, and it will be a lot helpful when we tomorrow
solve the question for, I would say arrays or strings.
Now if you see here the first function call is made for four.
And that is what even we have written.
Okay I think okay I forget to do one thing.
We should do that one second.
I forget to just basically increase this call equals one okay.
But anyways, I think that should be anyway helpful.
So we can see the next call is made for three.
Okay.
So we have also drawn two here.
The next call is for two which we can see here.
Then the call was made for one.
This is the one which is being talked about.
Next call after that is for zero which is actually coming here.
So this is the fifth call.
Then again this call is made for one which is your this one.
Right after that the next call is for two which is this one as we have written the seven here as well.
Like after this sixth, this call is made because this is still waiting in the I would say function
stack.
Then finally it is made for this one and this zero.
Okay.
So don't make the mistake where you are saying that four is going to call to three and then it's gone.
Then the third function call is going to get made to two.
No, that is not the sequence and recursion tree in total.
If you will try to make it for the first 510 problems, which you are going to do that is going to make
your concept in this a lot more clear.
Okay.
So now because you have corrected the code as well, if I run this now function call number.
Okay, I think I know the reason for this.
So it is just the scope of it and nothing else.
Yeah.
So now it's working everyone.
So just that we are we cannot change it.
We can use it if you want to change it, we want to make sure that it is, uh, in global scope.
Right.
We have to define and refer to it via global.
Uh, you must have learned of this in the scope of variables, okay?
If not, just make sure that you revise the classes.
And now you can see how this overall the classes like the calls and everything is going to get made
right.
Again, this thing is very important.
So please make sure that you draw this once as well.
Okay.
Now what we can do is just overwrite this here so that all of you can understand from this when you
see these notes.
Right.
So yeah, I hope with this this is clear.
Now let me just show you this by taking it a one step more further on the Python tutor, because that
will help you in visualizing a lot.
Okay, so pay attention everyone.
Now what exactly is going to happen first when we make the call?
First when we make the call one second.
So function call number one gets defined.
Now the function is going to get defined.
After that we are calling Fibonacci of four.
Okay four gets called four goes.
It will print.
That first function call is four.
It will check for base cases which is not the case.
So check base cases are not of course going to pass.
Then it is called for the last.
Okay.
So last it is going to call which is going to be three.
And you will see another Fibonacci function for three is basically going to get called.
So n is three here right.
Now if we move forward now if we move forward again the same thing is going to happen okay.
Now this whole function right.
This whole Fibonacci function is working for three.
For this block its going to go forward.
Check for base cases.
Of course that is not right.
Its going to call for its last which is two.
So it is actually if you will see just following this path.
Right.
The one which we have drawn here.
Okay.
So drawing this without actually running the code is very important.
And you will understand that once you keep on writing the code and you also see me drawing these trees
and explaining you all the questions.
Now, if we move forward, we will see that, okay, it is going to get called for the next part, which
is going to be going to check for base cases.
Okay.
Last is going to be one for this particular case.
One is the base case.
It's still going to print it.
One is going to be the base case.
So it's going to return one.
And the flow is going to go back to this particular function with value two.
Once it has gone to two it has gone the value of last as one.
It is going to get the value of last as one right.
So it is able to get this value.
And it's going to make the next call for second last.
So as of now here this value has been returned which is one.
And we are now going to call for second last which is going to be zero.
So once I call for zero, once I call for this zero, you can see that exactly.
It's also the base case.
So it's going to return one.
Similarly now it has got both the cases.
So N with two has got both the answer which is last and second last.
Both are one.
So it is going to return the answer which is going to be two.
Right.
So answer is going to be two.
And we can see that once we got the answer once we got the answer the function call with n is equal
to three.
Got the last value as two.
So it's going to call for second last which is going to be one for one.
Again it's going to return the value right.
It's going to return the value once it returns the value.
Of course we have to go forward.
We got the answer value for last and second last both.
And we're going to return the same as well.
Now our initial function with n is equal to four.
Got the value of last.
So it's going to make the call for second last.
And this is exactly the whole flow the way it is happening.
It's going to call call for second last.
So now Fibonacci is calling for two.
Two is going to subsequently make the call because it's not the base case.
It's going to make the call for one and zero.
Both of them are going to return value as one.
So we saw we see that it is returning the value as one.
In a similar way.
Second last for zero.
It is also going to get return the value of one.
So last and second last.
Both are returning one to ah this function with two on the right side.
So this two is the function which we are talking about.
So this one return the value as one zero.
Return the value as one.
And now using this particular thing, using this particular thing, what we will be doing is we will
be calculating our answer and return it to our main, the very first function.
So it has the last value already.
We are going to get the second last value.
Now once we get the second last value as well.
So three and two, we are going to find out our answer and return the same.
And our final answer is going to be five which we can see in front of us.
Okay, so great everyone.
I hope with this drawing of recursion tree by seeing this in the terminal, the answers as well as through
Python tutor visualization.
How to actually think about the recursion tree is clear.
Now what I want from you effectively is that for any problem which we are going to do as part of this
course, and along with few problems which you are going to try, which I am going to give you an assignment.
You have to make sure that you draw the recursion tree, even if it is clear, I still want you to draw
it, because this will help you to understand the concept of recursion a lot more.
And once you have done it for 10 to 15, I would say questions.
You will be a lot comfortable in that, and then you should be good to not draw and actually think of
the I would say answer and the tree in your mind and then you should you can basically move ahead with
that.
Right.
So yeah with that I hope uh, overall the concept of recursion tree is clear.
You have to make sure that while writing the code, we are not thinking of any of these.
That is for where PMI is, because you can think that if you keep like if you start thinking of this
thing when you are writing the code, how much time will you take for writing the code?
Right?
And I do not want you to do that, because in interviews, we have to make sure that we are able to
actually write an enable code and explain that.
And if the interviewer is is interested in understanding the same, we should be more than happy to
explain the full working and everything using recursion tree.
Okay, so cool everyone, let's meet in the next video where we are going to learn about and do some
more questions on recursion.