Hello everyone.
So I hope we are getting better idea about recursion now what we will do so we will solve many of those
problems so we can understand it better.
OK.
So today we will be solving fable not Cassidy's problem.
OK Phoebe anarchy cities so where does this happen knocking cities so 0 1 1 2 3 5 8.
So this is a fable knocking cities now.
What is if it were knocking cities so enough people knocking cities the first two numbers are fixed.
Now if you want to calculate any number that will be the sum of the previous two number.
So for calculating when what we will do we will add the previous two number.
Okay so zero plus 1 is when we want to find this number.
So it will be the addition of previous two numbers.
Okay.
We want to find this number so it will be the addition of previous two numbers.
We want to find it.
So addition of previous to number.
So what is it.
Addition of previous to number.
Now the cities will continue.
So eight plus five 13 13 blessed.
This will be 21 21 plus 13.
This will be 34 and so on.
Okay.
So what is our aim.
Our aim is to find and that we will not kill them but okay we have to find and net if you will not give
number.
So let's call it zero to Fukunaga number let's call it first if it will not get them.
And so on.
Okay.
So if I want to calculate sixth Fibonacci number so tell me 64 block number.
So this is zero.
This is 0 8.
This is first second third fourth fifth and sixth so sixth we we're not going number will be eight.
Okay so fib of six is eight six from an outgoing number is eight.
Okay.
So we have to find and net.
We will not get them but our goal is to find and net for we're not going.
Mystery I want to do something like this.
So if you want to call grid and network when I can.
But it will be the addition of previous to that is.
And net minus one who will not condemn and and that's minus from the Iraqi number and and that minus
two people not going in.
But okay so some of the previous two people not them but.
Okay.
So this is how we will be able to calculate and that's where we're not going no.
Okay.
And we can see this is recursion if I want to solve bigger problem then I have to solve smaller problem.
Okay.
So let's write code for it.
And these two are fixed.
Okay.
First two digits of difficult not number first two numbers of the Fibonacci guesses they are fixed they
are 0 and 1.
Okay so we have to use this formula and it's from an outgoing number is the sum of previous two people
not going number.
Okay.
So let's write the code for this so we will think only in terms of PMI.
So what a letter down typewritten that will be in danger.
I have to attend an danger that name of the function is fib.
It will take we have to find a network we in a month so it will take integer as input.
Now first of all what we have to do basic is okay.
So first is base case basic is the smallest problem whose solution we already know.
So if and in 0 so what is there to when I can no deal tracking number is 0 only.
Okay.
Now it's time for the recursion.
Okay recursive case
so we have to recursive case here.
Okay.
So small output 1 and small output 2.
So what will be small output 1 so a small output 1 will be and minus one people not them but that's
minus one to an ongoing number and small output will be it will be and minus two people are going number
and net minus second Copenhagen No.
Okay now it's time for the calculation
okay.
So in calculation what do you do.
I have done
submission of small output one in small output two.
Okay so this is all good very simple.
And now we have to call this function let's say I want to conclude it.
Third if you want I can add but okay I want to include We're not going no.
Okay so this is our computer code.
Now if we will run this code we will get at it.
Okay.
So let's first try to run this call and then I will explain you what do with added
so that it will be same so that it is segmentation fault at.
Okay.
So just like in the factorial we are having infinite loop here.
Now let us try to brighten our code to understand the problem.
Okay.
So the problem is seem like we get in the factorial in finite loop problem.
Now I want to calculate for we're not going number three.
Okay so let's write a novel code.
So I have three.
So what.
What will happen.
I am calling on to do will call on 1 when we will call on 0 now and then 0 so it will return 0.
So from here let's circle all this okay.
So these are the values often these are the values of an SO and is 0 1 and is it lambda attendings will
our base case.
Okay so I will return 0 from here.
Okay.
Now after this code this line will be executed.
So one will call on minus one okay then minus one will call on minus two minus two will call on minus
three minus three will call on minus four and so on.
Basically this will become infinite loop.
It will never stop.
Okay.
So what is happening here is obviously I want to if I wanted to calculate the first when I can and what
it would call in the previous two.
So it will call on zero and minus one.
Okay so this thing is obvious it will call in the previous two.
So this is obvious but what will happen it will never stop.
Okay yeah.
We will get infinite loop and our our loop will never stop.
Okay so what is the problem.
Problem is I am making two jumps so I have to take dubious cases.
We can see here I am making two jumps and minus 1 and minus 2 since I am making to them so I have to
take dubious cases here.
Okay.
And we know the first two feet were not in them but are fixed.
So first off we went not going but at 0 and 1.
So I have to add one more base case.
Okay.
So with one more base case will be if the value of and is one if I weren't to conclude the first few
lucky number.
So first we go knocking number is fixed and that is one only.
Okay now if you will learn our code of a code will run fine.
Okay.
So I want to read the third if it were not going and what.
Let us see what will be our output so our output is coming out to be 2 which is correct.
Okay now let's again but in our code so our output was 2 and this is Elvis's 0 and 1 so 0 plus 1 is
1 one plus one is two.
So this is the third if it will not be number.
So this is our output and our output is correct.
Okay now let us try to write another code and see what is happening.
So I want to calculate.
Third if we will not going number.
So this is third if it were not given but I went to a red card if we were not going in.
But now I will come here.
Okay so this tree will call on 2 and this is waiting at line number 15.
Okay.
And the value of ending quest tree is waiting at line number 15.
So what will happen.
Who will call on 1 No one is our base case.
So what will happen.
I will attend one from here.
Okay so this will return when.
So our small output 1 is 1.
Okay now it will call.
Now 2 will call on N minus 2.
So too will call on 0.
Now 0 is also a base case.
So it will return 0 it will returns it also.
This is our small output 2.
So our small output 2 is 0.
And then our calculation part I have to write the addition of these 2 so 0 plus 1 is 1 so too will return
1 2 3 okay.
Now what will happen 3 was waiting at line number 15.
Now it will call on line number 16.
So it will call on 1 Okay when is the base case.
So it will return 1 Okay so this one.
It was our small output when I was 1 output 1 is 1.
And this one is our small output 2.
So small output 2 is also 1.
And then I am returning the addition of these two small good one plus my output 2.
So I will return the addition of these 2 so when plus 1 is 2 so 3 will return to okay.
So two will come here and then we are printing 2.
So too is our answer.
Okay so that's how this code is working.
Okay.
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.
Okay.
Violating the code.
Think only in terms of PMI.
Okay.
You have to think about this diagram.
After writing the gold after writing the code you have to tango this diagram.
Okay.
So I suggest you do write in the code by making this diagram.
But first I write the code without thinking of this diagram.
Okay.
I'm repeating myself.
So first I have to write the code.
Thinking only in terms of PMI and second we have to write in our code.
And when we're done in our code we have to make this diagram.
Okay so first write code.
Second that in the code by making this diagram okay.
You do not have to think of this diagram first.
So this is secondary.
We have to tango this diagram later on.
First we have to write the code and violating the code we have to think only in terms of PMI.
So first the base case.
Second the recursive take case.
And third the calculation part.
Okay.
So I hope you understood this problem.
Okay thank you.