Hello, everyone.
So I hope you got the idea what is recursion?
Recursion is awesome.
Basically, it goes and says you want to find factorial and then find and minus one factorial first
by calling the same function and then using the result of N minus one factorial properly calculate and
factorial.
OK, the best part of recursion is it makes problem solving very, very easy for us.
We can find factorial iteratively.
Also iteratively means using the four or devi loop.
OK.
Going forward we will not think like.
Going forward, we will not think like Ford is calling three, three is calling to do is calling one
Anton.
The biggest problem of is people generally try to go in depth and then they face many problems and then
they got confused.
So to avoid that, let's look at the principle behind recursion.
OK, let's see how it works.
So recursion works on a principle that you guys have already studied and that principle is being my
principle of mathematical induction.
OK, so what is PMI?
So PMI was used to prove fact.
Let us take an example.
OK, so suppose there is a function F so function F is through.
For all natural numbers, OK, so this is an example.
So what PMI will do, BMI prove it in three steps.
OK, so there are three steps, so step one and step one.
But we will do.
We will prove.
That F of zero or F of one is true.
So this is the first step of BMI.
OK, BMI proves anything and effect in three steps.
So the first step is proof of 051 is true.
OK, so this means we can start with a very small number and prove that generally it's a very trivial
problem.
OK, simply just put the value.
OK, we will also take an example.
So this step is actually called Biscuit's.
Now, the second step of BMI is in the second step, what we will do, the name of the second step is
induction hypotheses.
So induction hypotheses, what we will do, we will assume, OK?
So what we will assume so, first of all, we have to assume you do not question it, OK?
Please don't question it.
We will always assume something.
So we are assuming we are assuming that FFG is true.
Workers are generally OK for any general.
Now, the third step of that third step of BMI is induction step.
OK, induction step.
So introduction step where people do.
Generally, in an action step, what we do is using the tool, so I'm writing here using step stepto.
Using Stepto, we will prove using Stepto.
We will try to prove that FFG plus one is true.
OK, so we have to prove two things, this one and this one, we have to prove based case and we have
to prove induction step.
OK, we can assume this one.
We can assume step stepto.
OK, we can assume step two, it is our hypothesis.
We do not have to worry about this, but we have to prove step one and we have to prove step three.
Step two, we can assume and please do not question it.
OK, so let us take an example and then we will solve that example with the help of FEMA.
OK.
So let's solve this very simple example.
So, Sigmon.
What is Sigmon segment basically means some of us to an natural number and there's a formula and in
doing plus one, why do some of us aren't natural?
No.
Now, let's apply BMI.
So in BMI, first step is the best case.
In the best case, what we will do, we will solve a very small problem.
So first step case.
So in this case, a four zero.
So what is above zero?
So Sigma Zero is basically some of zero actual number.
First to zero, national debt will be zero.
So this is our largest.
Now let's calculate averages.
So for our riches, this is our formula.
And now let us try to put an equal zero and equals zero here.
So zero and two zero plus one by two.
So this is this is zero.
OK, so this is averages.
So energises outages.
So we proved the base case, OK.
So we have proved four zero.
We can also prove it for one.
So now let us also provide for one.
So one so sigma one will be some of first an actual number.
It will be one only.
So this is our energies and our our averages will be so around 12 percent Birtwhistle one one plus one
by two.
So this is two by two and this is one.
And this is our averages.
So this is outages.
Hence we have proved our base case.
OK.
Our best guess is ready now, now the second step, the second step is induction hypothesis.
OK, so our second step is induction hypotheses.
So in induction, I put it, this is what we will do.
We will assume.
I can assume.
So what I'm assuming here, I'm assuming Sigma K is going to Cabletron by two.
Please do not question it.
I am assuming we just have to assume so what.
I'm assuming Sigma Sigma equals Cabelas and Mitu is true.
I am assuming this thing is true, OK?
So this is our mission.
OK, don't worry about it and please do not question this.
Now, the third step.
The third step is induction step, so in induction step, what we have to do, we have to prove we have
to prove what plus one.
So we have to prove that Sigma K plus one.
This is for the value.
So what we will do, we are.
We will put an equal K plus one.
OK, here we will put an equal shaped lesson.
So listen, this will become Gabler's two by two, OK?
So we have to prove this Sigma plus.
Segment gave listeners keep listening to Cabelas two by two now let us prove this.
So what is this?
We are solving allergies.
OK.
So Sigma K plus one, so can I write like this K plus one?
Plus, sick monkey, I can write it like this.
This is basically cape lesson.
So what is the value of the monkey?
So we can take the value of sigma market from here.
OK, so let's put the value of Sigma.
So this is going to a plus one by two, OK?
Now what we can do can multiply and divide by two here.
Yes, I can.
Then what I will do, take Gabe.
Listen to his comment.
OK, I am taking K plus one by two is common so we have two plus K so this is our allergist's and now.
Our allergies and allergies are equal, so allergies equals outages.
OK, so we have proved our third step, which is the induction step.
OK, so we have proved the base case, we have proved the induction step and we have assumed our induction
hypothesis.
Hence we proved that Sigma is added to in person by two.
OK, so proved has proved.
OK, so why it works, OK, how does it prove something?
So there is a very simple and awesome intuition behind this and what the intuition is.
So the intelligence is we have told you the starting position.
We have told you the base.
We have taught you how to take next step from one step.
Now, from the base, from the base, we can use this thing.
To go to the next step, to go to one step ahead, and then we can prove this step and then we can go
to the next step, then we can prove this step and then we can go to the next step and so on.
OK, so this was the basic condition.
Now let's see some math also.
OK, let's see some math also.
So what we have done here is so if K equals zero.
So game means basically and only so if N equals zero.
So this we have proved this was our base.
We have proved four and equals zero, so this we have proved.
OK, now the second step, which was the induction hypothesis.
OK, so inside the induction, I put this step if Gaikwad zero, what did I assume?
I assume that is true.
Now, this now this thing we assumed in the election, I put to this step, but what I am saying here
is the value of zero, OK, the value of Kizito inside the index.
And I put this step.
So that means of zero is true.
So first of all, this is not assumption, this we have proved.
OK, this we have proven the base case, this is not our inception, if zero is true, this is not an
assumption.
This is a fact.
OK, I'm not assuming anything here.
We have already proved this in our best case.
Now, the next step inside the next step.
What did I proved?
I proved that if it was true, then FFG plus one is also true.
This thing I approved for attorney general.
OK, I have proved this thing for any general.
If it is true, then F of K plus one is also true.
Now the value of K zero.
So far, zero is true, that means using the index step of one is also true.
OK, because we have proved this for a general.
Now, if one is true, then of two is also true.
Using the induction step, if true is true, then that is also true, then it is also true, then FIFA
is also true and this way we can go up to end.
OK, so finally, what we can right here, we can write FSN is true and we have to prove this only.
So we have proved in this way.
OK, so we came here to using when using do we go to try using three, we go to four and so on.
So in every occasion problem you have to think like this only, OK, in every occasion problem you have
to think you are applying BMI to prove a term.
I'm repeating myself in every occasion problem.
What we will do, we will think that we are applying BMI to prove a theorem.
OK, so first of all, in every occasion problem, but we have to do to solve any problem, we have
to do three simple things.
So the first thing is we will think we will we have to think about the best case.
OK, very simple case.
We have to think about the best case.
Now, the second thing is, I don't have to worry for the smaller problem, OK, in the second step.
We don't have to worry for the smaller problem if I have to work for and then I'm going to assume it
works for and minus one.
So assume you have a solution for the smaller problem.
Solution assumes smaller problem solutions already.
Did you just have to use their solution to solve the bigger problem?
If I'm able to do that, then be a mice's your Cordwell work permit guarantees that your code will work
OK.
And I will not think all this like fact for is calling three.
Three is calling to on.
OK, I will not take all this so we will directly think for an OK, we will directly thank for N because
we will assume we have and minus one.
Now using that assumption I need to propolis all 14.
OK, so let's write factorial and again.
But this time we will think in terms of PMI, ok.
So I am writing factual function again, but this time we will think Orlin p.m. items.
So first of all, what the return type that will be under the name of the function is Vectorial fact,
it will take our indigenous input.
Now, the first step of an education problem, thinking payment items only.
OK, what is the first step?
The first step is the best case.
Very small problem.
So you can take so if any equals zero, what is a factual four zero factual answer is one zero, factual
is one.
You can also write for one on one also.
OK, if I equals one, then also return one.
So let's have a tweet.
So our best is ready.
Now, what we have to do is take a step of PMI is induction hypotheses.
You have to assume so I am assuming.
Then I have my answer for 10 minus one.
OK, so this is our assumption, no, please do not question this, OK, so this is assumption.
OK, so suppose this function for both function works, so I'm giving the function a smaller input,
it will give me the answer.
OK, do not question this line.
OK, please do not question this line.
You have to assume this.
OK, so this is our assumption.
It is also called the recursive case.
OK, now what we have to do, we have the answer for and minus factorial, now we have to properly calculate
the answer for and factorial.
So this will be and multiply.
And multiply, Smolan said.
OK, we have to properly calculate, OK, so this is our third step.
This was the third step of the third step for solving any immigration problem.
OK.
This was the second step.
And this was the first to step.
So first step is basically the second step is assumption, which is also called recursive case, and
that third step is the calculation.
OK, so third step is.
Calculation.
Now we have our own sanity and we can do it on our own set.
OK, now let's call this function so called.
Federal food.
OK, let's go now file, let's read the good.
So output is 24 for Vectorial, and of course, our goal is working.
Now see here we are not thinking like Ford is three.
Three is calling to do is calling when we are not going in depth.
OK, think only in terms of PMI.
Remember to step first step.
Simple, very simple.
Biscuit's second step assumption, which is the recursive keys.
Third step is the calculation.
OK, you have the answer for the smaller problem now with the help of the answer of the smaller problem,
calculate the big answer and then return the big answer.
OK, simple enough.
So there are three steps.
First is the best case.
Second is assume it will work for the smaller problem.
OK, third step is properly called for the bigger problem.
Three simple steps I am repeating.
First base case.
Second, assume it will work for this problem.
Third, properly called for the bigger problem.
OK.
This is very simple.
Called.
OK, thank you.