Once you have identified that you can solve a coding interview question using recursion, the most important
step to proceed further is to be able to draw the recursion tree.
You will see that if you can do that after you are done with drawing out the recursion tree, you will
be able to easily solve the question and code it out.
So let's go ahead and practice drawing a simple recursion tree.
Now this over here is going to be a very simple one, and we will keep drawing recursion trees as we
go along with the course.
So let's say you want to draw the recursion tree for the Fibonacci series.
Now a quick setting of the context over here.
The Fibonacci series can be defined as f of n is equal to f of n minus one plus f of n minus two.
And it's also given that f of zero is zero and f of one is one.
Now what does this mean?
Let's write out the sequence to understand this.
So the first term is zero and the second term is one.
So let's write the two terms.
All right.
Now it's given over here that the next term is the sum of the previous two terms.
So f of if this is zero, this is one f of two would be f of one plus f of zero.
And we know the values of f of zero and f of one which is zero and one.
So this value over here which is f of two would be zero plus one which is equal to one.
Again, the next term over here would be the sum of these two previous terms.
So f of three would be equal to two.
Similarly f of four would be two plus one which is equal to three.
And it goes on in this manner.
All right.
So this is the Fibonacci series.
All right.
Now we will see this in a future video in detail.
But over here we are just trying to try out drawing the recursion tree for this interesting question.
So let's get started.
All right.
So let's say we're going to start with F of three.
Okay.
So let's say we want to find the value of f of three.
So the code calls f of three.
And this over here is going to recursively call f of two and f of one okay.
So it's going to call f of two.
And notice that before it goes to call f of one this f of two itself will recursively call f of one
and f of zero.
Right.
So this is f of one.
And first it's going to call f of one.
And because we already know the value of f of one it's going to return the value which is one okay.
And then f of two is going to recursively call the function f of zero.
Again we already know the value of f of zero.
So it's going to return zero.
And now f of two can be calculated, which is one plus zero which is one.
Therefore, f of two is gonna return one to f of three.
Okay.
So f of three is f of two plus f of one.
We have seen that right.
So first it will go down to this part over here it will try to calculate f of two.
Again f of two will recursively call f of one.
And because this returns it will go to the other branch call f of zero.
Get back the value.
And it's it's done with getting back the values needed and it will return the value one.
Now f of three is going to call f of one.
And we already know that f of one is already computed.
So it's going to return one.
And then f of three is going to return one plus one which is equal to two.
So this over here, what we've drawn out over here is the recursion tree.
Now, once you are done drawing out the recursion tree, it's very easy to go ahead and code this out.
Now, in simple terms, the pseudocode would be just that if n.
Is less than or equal to one.
We already know the value, right?
So if n less than or equal to one, we just need to return n itself, because for zero the value is
also zero.
For one the value is also one, right.
And for other cases we just need to return f of n minus one plus f of n minus two.
Again, we are.
We are not aiming to write the detailed pseudocode over here.
I'm just giving you a sample over here.
We will see this in a future video in great detail.
But over here we are just getting introduced to drawing a recursion tree.
If you can successfully draw the recursion tree for a recursion problem, you will find that it will
be a very easy task to go ahead and code it out.
This is especially true for complex questions.