Hello, everyone.
So I hope we are getting better idea about recursion now, what we will do so we will solve many Aghajan
problems so we can understand it better.
OK.
So today we will be solving Funaki serious problem.
OK, Funaki cities.
So what is happen, because it is so zero one one two three five eight, so this is a fable, I guess
it is.
Now, what is a fable?
Because it is so in the Fibonacci series, the first two numbers are fixed.
Now, if you want to calculate any number, that will be the sum of the previous to number.
So for calculating when what we will do, we will add the previous two numbers.
OK, so zero plus one is one.
We want to find this number.
So it will be the addition of previous to numbers.
OK, we want to find this number.
So it will be the addition of previous to numbers.
We want to find it so addition of previous to number.
So what is it addition of previous to a number now the series will continue, so eight plus five, 13,
13 plus eight, this will be 21, 21, plus 13.
This will be 34 and so on.
OK, so what is our aim?
Our aim is to find a net Fibonacci number.
OK, we have to find a net Fibonacci number.
So let's call it zero Fibonacci number.
Let's call it first Fibonacci number and so on.
OK, so if I want to calculate sixth Fibonacci number, so tell me sixth number.
So this is zero.
This is zero.
This is first, second, third, fourth, fifth and sixth.
So sixth number will be eight.
OK, so first off, six is eight.
Six for number is it.
OK, so we have to find a net.
We will not get them, but our goal is to find a net for them.
But basically I want to do something like this.
So if you want to call grid and network number, it will be there the previous to.
That is a net minus one.
And and that's minus no end and net minus two.
OK, so some of the previous two Fibonacci number.
OK, so this is how we will be able to calculate and that's what we're not going number.
OK, and we can see this is recursion.
If I want to solve a bigger problem then I have to solve a smaller problem.
OK, so let's write code for it.
And these two are fixed.
OK.
First religious of the first two numbers of the Fabianski says they are fixed, they are zero and one.
OK, so we have to use this formula.
And that's what talking about is the sum of previous two people not get no.
OK, so let's write the code for this.
So we will think only in terms of BMI, so what a letdown by Britain that will be in.
I have to return in the name of the functionalism it will take.
We have to find a network in a month.
It will take our indigenous input.
Now, first of all, what we have to do best case, OK?
So first is basic, is basic, is the smallest problem, the solution?
We already know.
So if.
And is zero.
So what is the number, the number is zero only.
OK.
Now it's time for the.
OK, recursive case.
So we have to recursive case here.
OK, so small output one and small output to.
So what will be small output, one, so small output will be?
And minus one Fibonacci number, and that's minus one, two and number and small output will be.
It will be.
And minus two, not going to buy a net minus second for.
OK, now it's time for the calculation.
OK, so in conclusion, what do you do?
I have to return.
Submission of small output one and small output two.
OK, so this is very simple and now we have to call this function.
Let's say I want to calculate Toadfish when I can.
No.
OK.
I want to 131.
No.
OK, so this is our computer.
Now, if we will run this code, we will get error.
OK, so let's first try to learn the score and then I will explain you what will be their.
So there will be same so that it is segmentation, fault error.
OK, so just like in the factorial, we are having infinite loop here.
Now, let us try to pretend our goal to understand the problem.
OK, so the problem is seem like we get in the factorial infinite loop problem.
Now I want to calculate Fibonacci number three.
OK, so let's write a novel code.
So I have three.
So what what will happen?
I am calling on to.
We will call on when when will call on zero now and zero, so it will return zero.
So from here, let's circle all this.
OK, so these are the values often these are the values of so and zero, when it is returning our back
is OK.
So I will tangelo from here.
OK, now, after this cold, this line will be executed.
So when will call on minus one?
OK, then minus one will call on minus two, minus two will go on minus three, minus three will go
on minus four and so on, basically this will become infinite loop.
It will never stop.
OK, so what is happening here is obviously I want to if you want to calculate first, we're not going
to recall on the previous two, so it will call on zero and minus one.
OK, so this thing is obvious.
It will call on the previous two.
So this is obvious.
But what will happen?
It will never stop.
OK, we are we will get infinite loop and other our love will never stop.
OK, so what is the problem.
Problem is I am making two jumps so I have to take two because we can see here I am making doorjambs
and minus one and minus two since I am making to them.
So I have to take two cases here.
OK, and we know the first two are fixed.
So first of all numbers are zero and one.
So I have to add one more base case.
OK, so the one more base case will be.
If the value of.
And is one, if I want to calculate the first Fibonacci number.
So first number is fixed and that is one only.
OK, now if we will run our code of a quarter million, fine, OK?
So I want to calculate the third.
We're not let us see what will be our output.
So our output is coming out to be two, which is correct.
OK, now let's again bring our called.
So our output was to and this is obviously zero and one, so zero plus one is one one plus one is two.
So this is the third Fibonacci number.
So this is our output and our output is correct.
OK, now let's try to try another gold and see what is happening.
So I want to calculate Fibonacci number.
So this is terrific, but I want to convert it.
But now I will come here.
OK, so this tree will call on two and this is waiting at line number fifteen, OK, and the value of
three is waiting in line number fifteen.
So what will happen to will call on when.
No one is our base case, so what will happen, I will return one from here.
OK, so this will return when so our small output one is one, OK, now it will call now two will call
on minus two, so two will call on zero.
Now, zero is also a base case, so it will return zero.
It will return also.
This is our small output to show our small output to is zero and then our calculation part, I have
to return the addition of these two.
So zero plus one is one.
So two will return.
One, two, three.
OK, now what will happen?
Three was waiting at line number 15.
Now it will call on line number 16.
So it will call on when.
OK, when is the best case, so it will be one.
OK, so this one, it was our small output, one salis, one output one is one and this one is our small
output two.
So small output two is also one.
And then I am returning the addition of these two small children, plus more output do.
So I will return the addition of these two.
So one plus one is two.
So three will return to.
OK, so two will come here and then we are printing two.
So, too is our answer.
OK, so that's how this code is working.
OK, so one thing that I want you to do is think of all this.
So one thing that I want you to do is think of all this after writing the code, OK, violating the
code, think only in terms of PMI, OK, you have to think about this diagram after writing the code,
after writing the code, you have to take out this diagram.
OK, so I suggest you do try it in the code by making this diagram.
But first write the code without thinking of this diagram.
OK, I'm repeating myself.
So first I have to write the code thinking only in terms of PMI.
And second, we have to try it in our code.
And when we're done in our code, we have to make this diagram.
OK, so first write code.
Second that in the code by making this diagram, OK, you do not have to think of this diagram first.
So this is second.
We have to tangoed this diagram later on.
First we have to write the code and violating the code.
We have to tangle in terms of PMI.
So first, the best case.
Second, the recursive case and third, the calculation part.
OK, so I hope you understood this problem.
OK, thank you.