So we want to continue our discussion on recursion.
And today we are going to learn about a very important series which you can do via recursion.
That is the Fibonacci series.
Now, I am pretty sure that till now you will be getting some hang of recursion, like you will be understanding
what exactly it is and how to solve question using the same.
In the series of lectures which will follow, I will be mainly focusing on solving questions with you
and showing you the exact way, as well as help you visualize that how exactly things are happening
in the back end.
Understanding the same.
I'm pretty sure that once you understand that properly, you will be able to solve the question by using
the concepts of recursion yourself as well.
Now let us start with Fibonacci series.
So Fibonacci series is a very good, I would say example as well as application of recursion concept.
Now first let me tell you what exactly the series is.
So let me write the series.
So this is your Fibonacci series.
Now what exactly it is some like any particular position right?
At any any particular position, the number is given by sum of last two numbers.
So for example for this three it is equal to one plus two.
Five is equal to two plus three.
So in this manner we are getting our number.
A particular number can actually be provided by some of its last two number.
The question actually is given us in a way that we have asked that okay, tell me which.
Tell me this particular number.
So let's say if this is zeroth number, this is first, second, third, fourth, fifth, sixth.
So if let's say someone is asking me, hey, can you tell me which is the fourth Fibonacci number?
Yes, you can tell and you can give the answer as five.
In a similar way, you can tell ninth number, 10th number.
And like in a similar way, any number which is required.
Some people start the series from zero, but that won't have any effect.
So you can start from either 0 or 1.
I am starting it from one now.
I hope this series is a lot clear, right?
So the recurrence relation for this series is also, I would say very easy to write.
So let me write the same for you.
Fibonacci of any given n is equals to.
If you provide me with the last Fibonacci number and Fibonacci of second last number, right?
So what effectively I am saying is that, hey, you just get me the last number and the second last
number.
So this in a way becomes a see, this in a way becomes a recursive problem, right?
So because I can present my solution as part of some smaller problem and that is how we have learned
about recursion.
So now let us see how we are going to solve it.
Now again because we have I would say learned about PMI.
We will be again using the same.
But I want to just show you once an extended form of PMI, that will be a lot helpful because as of
now, we have just seen cases or quotients where we had a single dependency on single, I would say
recursive function, right?
So here if you will see we have two of these functions.
So we I know that we I can assume for this, but can I also assume for this.
That's the question.
Right.
So let us see the same everyone.
So PMI extended form.
The first I would say step is the same.
We have to prove for our base case that if f of zero or f of one, right.
So that thing is exactly the same.
The change happens in the second part in this.
What the second part is saying that assume again, I have made sure that I am highlighting it specifically
because you have to assume assume for f I equal to true.
Okay.
So this time it's saying that you can assume for f of I where I can be from zero to k.
Okay.
So earlier I was just asked to assume for f of k.
But now it is saying that I can assume it true for everything starting from zero to k.
Okay.
So okay, let us understand how has it how we can do that.
How can we assume the same thing.
Okay.
So that it basically means that we can assume for f of k true f of k minus two and everything.
Right.
So let us understand that once okay.
So that it is clear to you.
Now if you are like if you see the first step, we know that f of zero is true.
Right.
Now taking this as a base case or taking this as the first step, I can actually prove for f of one.
So for f of one what I will be doing is I can take k is equals to zero.
Now I am assuming k is equals to zero.
My base case is also f of zero.
Using that I can prove for f of one yes or no.
So again I am just applying PMI here.
Using the base case as well as f of k is equal to zero.
Okay.
Where my k is now equal to zero.
I can prove it true for f of one is true.
Great.
So now if I want to prove for f of two I have my base case.
I have my base case which is f of zero.
I have for k is equal to one I have my f of one is also equal to two, which I have already proven.
I can then similarly prove f of two is equal to zero or sorry, f of two is true.
That is something which I can use and prove for any function just using the principle of PMI.
Now going forward for f of three if I want, because I have proven all of them.
Because I have proven F of one zero, one, two.
Basically for all zero to k, I can actually say, I can actually say and use any of these and prove
that f of three is going to be true.
Now, if I similarly go forward and see, let's say F of four was my final thing, which I wanted to
prove right.
Let's say I want to prove for F of four.
Now it's on me, right?
If I can use f of zero, f of three, f of one, like why should anyone have a problem?
Because I have proven each and every thing below my F of four is two.
So what does that transform is to is that let's say if you want to prove for F of 50, right.
If let's say n is equal to 50, then you can actually assume for all from f of zero to f of 49, you
can assume that each and everything is true there.
What's the overall I would say outcome of this particular thing is that as of now, as of now, I was
just assuming that my last.
Okay, so let's say my f of n minus one I can assume to be true, but this extended form have actually
made my framework a lot more stronger.
And I have also proven to you that, okay, how exactly can I do that?
It's just a step by step taking process where I'm proving each and every one of them right, using PMI.
And then for a particular I would say case, I can use all of them because I have proven all of them
to be true.
In a similar way, I can now actually prove use for f of n minus two as well.
So I can just also assume for second last to be true.
And that's the exact reason that is actually how I want you to explain.
And not just, I would say assume that you will also get for f of n minus two?
No.
So here if you will see we have a dependency on f of fib of n minus two as well, right?
This extended form.
This extended form is actually giving us the power through which we can assume for n minus two as well.
Okay.
So I hope this is clear.
Again I will repeat the step.
First we have to prove for base case or rather basically we know that okay base case is there.
Then earlier we were just assuming for f of k.
But now I am saying, and I have proven the same to you, that you can now prove for everything from
zero till K, and that's the reason that I can actually ask my recursion to get me the answer for n
minus one, as well as n minus two.
And I can assume yes, that answer is going to be true.
Okay.
So now let us quickly write the code for that.
Like let us try to basically just write it in code.
So this is Fibonacci function which I have already written and I'm asking for shy of four.
So what I will be doing is if my n is equal to equal to zero, this is my base case.
I know the answer is going to be one so I can return one.
Now I can get the last, which is going to be Fibonacci of n minus one.
Using the extended form of PMI.
Now again, here is something which I want you to explain very specifically using extended form of PMI.
I can also ask for second last as well.
And I know that that it's going to be true.
Now my answer is going to be last plus second last.
And I can return this answer and I can return this answer.
Okay.
So let us try to run this.
Now many of you might be thinking that it might not run.
So let us see.
Some problem is there but we want to fix it.
Okay.
So when I run it it's showing that recursion error maximum recursion depth exceeded.
I think we have seen this error right.
We have actually seen this error somewhere earlier when we were trying to learn recursion, we saw this
error where the case like it is making infinite calls.
So that is where depth gets exceeded.
So let us see what exactly is happening.
Right.
Let us see what exactly is happening by printing the n.
But meanwhile let me also show you the same.
So let me just quickly make the tree for this n is equal to four.
So.
For four it's going to make the first call to three.
Three is going to make the call to two.
Two is going to make a call for one, and one is going to make a call to zero.
This is going to return you the answer because it's the base case as one.
And now this is going to go for minus one because it's going to call for second last as well.
So this is the last call.
This is all the last call for the last number.
And this is for the second last number.
Now this minus one.
It's a problem right.
We don't have a minus one as a number.
And again this is going to call for minus two going forward.
This is going to call for minus three.
And you will see that exactly.
This is going to be the call structure okay.
So let me just print n and let me try to run this and see 43210 minus one minus two minus three.
And all the way it's going down okay.
Now why is this happening exactly.
The reason is that, uh, if you will see that I've just given you a single number.
Okay?
I have just given you a single number.
Does it make sense that.
Okay, I'm giving you a one number in the starting?
I'm giving you just one number in the starting.
Let's say it is one.
And I'm asking you to give me the next number now.
Fibonacci, as in nature, is defined that anything is actually the sum of last two numbers, right?
So in this particular problem, again that is also one very important caveat in this problem, which
I want you to explain that in this particular problem we will have two base cases because to begin with
in a Fibonacci number or Fibonacci series, I have to make sure I always have to make sure that I have
two numbers to start with.
How can I provide you with the answer or with the third number if you have not given me the first two
numbers?
Because this third is actually dependent on both of them, right?
So again, we have seen that this question is different and very important in two aspects.
Here there are two base cases because I have dependency on two of them.
Similarly I have last and second last right.
I have last and second last, which you can now assume to be true because I have shown you that via
PMI extended form.
Okay, I have explained you that, okay, how we can do that, how we are good to use that.
And that is where this question becomes a lot important.
Okay.
And now I think this question will work absolutely fine if I run this for, let's say for.
Let me just comment this one second.
I think it's not saved.
So we have not added that.
So if n is equals equals to one we can just return one as well.
And now it's giving me the number which is five which I think is the right answer.
So yeah fourth is the five okay.
So this works now.
Now for this particular case as of now also I will not leave you.
And we are going to draw a recursion tree for this.
Now this problem is a little bit different.
So I want to make sure that you are able to understand how the calls are going to be, which function
is going to get called in which sequence.
So in the next video I'm going to draw the recursion tree for this.
And you have to understand each and every thing as well as the sequence in the way this particular function
is calling.
I would say for which particular number or n the functions are going to get called.
That thing again becomes a lot more important based on the code which we have written.
Okay.
So great everyone, uh, that I hope that was clear.
Please make sure that you try to just draw this tree once yourself as well for this particular problem
for okay.
And I'm going to make sure that I explain that properly to you in the next video.
Thank you.