Hello everyone.
So I hope you get the idea.
What is recursion recursion is awesome.
Basically we go Genesis.
You want to find factual and then find and minus one factorial first by calling the same function and
then using the result of and minus one factoid properly calculate and factorial.
Okay.
The best part of recursion is it makes problem solving very very easy for us.
We can find factorial identically also.
I literally means using the four or Devi loop.
Okay.
Going forward we will not think like going forward we will not think like four is calling three threes
calling to do is calling 1 and so on.
The biggest problem with recursion 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.
Okay let's see how it goes in books.
So recursion works on a principle that you guys have already started and that principle is being my
principle of mathematical induction.
Okay so what is BMI.
So BMI was used to prove fact.
Let us take an example.
Okay so suppose is a function f so function F is through for all natural numbers.
Okay.
So this is an example.
So what BMI will do BMI prove it in three steps.
Okay.
So there are two steps.
So step one and step one but we will do we will prove that F of zero or F of 1 is true.
So this is the first step of BMI.
Okay.
BMI proves anything.
And effect in three steps.
So the first step is prove f of 0 F of 1 is true okay.
So this step means begin start with very small number and prove that generally it's a very trivial problem.
Okay simply just put the value okay.
We will also take an example.
So this step is actually called biscuits.
Now the second step of BMI is in second step.
What we will do.
The name of the second step is induction hypotheses so in induction hypotheses what do we do.
We will assume Okay so what we will assume.
So first of all we have to assume you do not question it.
Okay.
Please don't caution it.
We will always assume something.
So we are assuming we are assuming that f of K is true where gays are generally okay for any general
gay.
Now the third step of that third step of BMI is induction step okay induction step so in induction step
what we will do generally in induction step what we do is using that too.
So I am writing here using Step Two using Step two we will prove using Step two we will try to prove
that f k plus one is true
okay so we have to prove two things this one and this one we have to prove base case and we have to
prove induction step okay we can assume this one we can assume Step Two okay we can assume Step 2 It
is our hypotheses we do not have to worry about this but we have to prove Step 1 and we have to prove
step t Step 2 we can assume and please do not question it.
Okay so let us take an example and then we will soil that example with the help of BMI Okay so let's
solve this very simple example so Sigma and what is segment segment basically means some more fast and
natural number and there's a formula and in doing plus one by two.
Okay.
Some of the first and natural number.
Now let's apply BMI so in BMI.
First step is the base case in the base case what we will do we will solve very small problem.
So first step.
Base case so in base case f of 0.
So what is f 0 so Sigma 0 is basically sum of zero natural number first is our natural number that will
be zero.
So this is our largest.
Now let's calculate outages.
So for outages this is our formula.
And now let us try to put an equal 0 so n equals zero here so zero and to zero plus one by two.
So this is this is zero.
Okay so this is outages.
So logistics outages.
So we proved the base case.
Okay.
So we have proved 4 0.
We can also provide for 1 2.
Now let us also provide for 1.
So 4 1.
So sigma 1 will be some 0 first one natural number that will be 1 only.
So this is our allergies and our right to our allergies will be so and into an investment by.
So when one plus one by 2.
So this is 2 by 2 and this is 1 and this is our allergies.
So allergies is outages.
Hence we have proved our base case.
Okay.
Our base case is ready now.
Now the second step the second step is induction hypotheses.
Okay.
So our second step is induction hypotheses.
So in induction I put it this what we will do.
We will assume I can assume.
So what I'm assuming here I'm assuming Sigma okay is keen to Kate Plus One By Two please do not question
it to why I am assuming we just have to assume.
So what I'm assuming Sigma okay.
You said Mark equals Kate plus on might do is true I'm assuming this thing is true.
Okay.
So this is our exemption.
Okay broad worry about it.
And please broad 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 40 plus 1.
So we have to prove that Sigma K plus 1 This is for the value.
So what we will do we are we will put an equals K plus 1.
Okay here we will put an equal escape lesson.
So K plus 1 this will become K plus two by two.
Okay.
So we have to prove this Sigma K plus 1 sigma Kate plus 1 is keep listening to K plus two by two.
Now let us prove this.
So what is this.
We are solving allergies.
Okay so segment K plus 1.
So can I write like this.
K plus 1 plus sick monkey.
I can write it like this.
This is basically K plus 1.
So what is the value of sick mucky so we can take the value of sigma came from here okay so let's put
the value of sigma okay.
So this is gain do K plus 1 by 2.
Okay.
Now what we can do can and multiply and divide about 2 here.
Yes I can then what I will do.
Take Gabe listen my 2 s comment Um okay I'm digging K plus 1 by the way is common.
So we have 2 plus K so this is our largest and now our largest and outages are equal.
So a logistic equals outages okay.
So we have proved our third step which is the induction step.
Okay so we have proved the base case we have proved the induction step and we have assumed our induction
hypotheses.
Hence we proved that Sigma n is added to in person by okay.
So proved hence 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 intuitions is.
So the indulgences 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 next step to go to one step ahead.
And then we can prove this step and then we can go to next step.
Then we can prove this step and then we can go to next step.
And so on.
Okay so this was the basic contusion.
Now let's see some math also.
Okay let's see some metal also.
So what we have done here is so if gay equals zero so gay means basically and only so if any equals
zero.
So this we have proved this was our base we have proved four and equals zero.
So this we have proved okay.
Now the second step which was the induction hypothesis step.
Okay.
So inside the induction I put this step if gay equals zero.
What did I assume I assume that f off gay is true.
Now this.
Now this thing we assumed an induction I put to this step.
But what I'm saying here is the value of k 0.
Okay.
The value of k 0 inside the induction I put this step.
So that means F of zero is true so first of all this is not assumption.
This we have proved okay.
This we have proved the base case.
This is not our inception.
F of 0 is true.
This is not an assumption this is a fact.
Okay.
I am not assuming anything here.
We have already proved this in our base case.
Now the induction step inside the induction step.
What did I approved.
I approved that if F of case true then f of K plus 1 is also true.
This thing I approved for any general gay.
Okay I have proved this thing for any general Okay.
F F off gays true then f of gay plus 1 is also true.
Now the value of k 0 so f of 0 is true.
That means using the index in step f of 1 is also true.
Okay because we have proved this for a general G no f f of Venus true then f of 2 is also true using
the induction step f f of 2 is true then f of TS also true then 4 is also true then 5 is also true.
And this way we can go up to and okay.
So finally what we can write here we can write f often is true and we have to prove this only.
So we have proved in this way okay.
So we came out to using when using do we go 2 3 using 3 we go to 4 and so on.
So in every recurrent problem we have to think like this only okay in every cogent problem.
You have to think you are applying PMI to prove it to them.
I am repeating myself in every cogent problem.
What we will do we will think that we are applying PMI to prove a totem.
Okay so first of all in every occasion problem what we have to do to solve an integration problem.
We have to do two simple things.
So the first thing is we will think we will.
We have to think about the base case.
Okay very simple case.
We have to think about the base case.
Now the second thing is I don't have to worry for the smaller problem.
Okay in the second step We don't have to worry for the smaller problem.
If I have to work for n then I'm going to assume it works for and minus one.
So assume you have a solution for the smaller problem solution assumes.
While the problem solutions already did you just have to use their solution to solve the bigger problem.
If I am able to do that then be a Macy's.
Your code will work.
BMI guarantees that your code will work.
Okay and I will not think all this like fact for is calling 3 3s calling 2 and so on.
Okay I will not think all this so we will directly think for an okay.
We will directly think foreign because we will assume we have and minus one.
Now using that assumption I need to properly solve for then.
Okay so let's write factorial and again but this time we will think in terms of BMI.
Okay so I am writing factorial function again but this time we will think only in BMI items.
So first of all what do the return type they return.
They will be in danger.
The name of the function is factorial fact.
It will take AI Indigenous input.
Now the first step of an integration problem thinking BMI terms only.
Okay.
What is the first step.
The first step is the base case.
Very small problem.
So you can take.
So if any equals zero.
What is effectual for zero factorial.
The answer is 1.
Okay zero effect or Lisbon.
You can also write for one on one also.
Okay.
If any equals 1 then also return 1.
So that's our trade.
So our base case is ready.
Now what we have to do.
Second step of PMI is induction hypotheses.
You have to assume so I am assuming that I have my own set for then minus 1 OK so this is our assumption
now please do not question this.
OK so this is assumption.
Okay so suppose this function for all function works.
So I'm giving the actual function a smaller input it will give me the answer.
Okay.
Do not caution this line okay.
Please note caution this line.
You have to assume this.
Okay.
So this is our assumption it is also called a recursive case
okay.
Now what we have to do we have done set for and minus in fact total.
Now we have to properly calculate the so for and factorial.
So this will be an multiply and multiply small onset okay.
We have to properly calculate.
Okay.
So this is our third step.
This was the third step of being my third step for solving any recursion problem okay.
This was the second step
and this was the first to step
so first step is basically base case.
Second step is assumption which is also called recursive case.
And the third step is the calculation okay.
So the third step is
calculation where we have our answer ready and we can draw done either on set okay.
Now let's call this function to see out federal food
okay.
Let's go now file.
Let's run the called so our output is 24 for factory list 24 so our code is working.
Now see here we are not thinking like 4 is calling 3 3 is calling to do is calling when we are not going
in depth.
Okay.
Think only in terms of PMI remember three step first step.
Simple very simple biscuits.
Second step assumption which is the recursive keys.
Third step is the calculation.
Okay.
You have done so with a smaller problem now with the help of the answer of the smaller problem.
Calculate the big answer and then return the big answer.
Okay.
Simple enough.
So there are two step.
First is the base case.
Second is as you know it will work for the smaller problem.
Okay third step is properly called for the bigger problem.
Three simple step.
I am repeating first base case.
Second assume it will work for the smaller problem.
Third properly called for the bigger problem.
Okay.
This is very simple called okay.
Thank you.