Hello all and welcome back.
So we are going to continue our discussion on recursion.
And I am going to teach you the underlying principle of recursion that is PMI.
Now I hope till now you are getting some idea about recursion like you are actually feeling.
How awesome is it, right?
So let's say we have to find a factorial so we don't have to do anything.
We just have to call the same function, ask it to give me the answer, and I can just use and multiply
it by n and give back my answer.
Now yes, these problems can be done iteratively, but few of these problems like okay, we will still
be using recursion to get the mastery.
And as we go forward, I'm going to show you more of, I would say, problems which actually can just
be done by recursion only.
Right.
So there are a lot easier if we do that via recursion.
Now the main problem with recursion, which I fell for, and even I see most students like who are learning
it falling for is that we try to do go a lot deep into recursion, right?
So as of now, even I am trying to show you by making 2 to 3, three times the core function calls and
everything.
Okay, so what happens is that whenever they are presented with a question where they find out that,
okay, recursion is to be used.
They take a lot of time, right?
They are actually drawing and finding out cases and making everything.
And that is the I would say biggest mistake which you can do if you are solving recursion.
So to understand more on that we have to understand the major, I would say the basic principle on which
recursion lies, and that is nothing but principle of mathematical induction PMI okay.
So recursion principle is based on PMI.
So understanding this will further help us to master recursion.
And believe me when I say this is very very important okay.
So if you understand this once this is going to be a lot helpful to you in writing the code for your
recursion okay.
So now let us see what PMI actually is.
So I have written a beautiful handwritten notes for that.
Now PMI actually like is taught in schools.
So in the school textbook normally it is taught but because it's a very small chapter we don't pay a
lot heat of that.
But yes PMI is something which we have most probably must have already been I would say learned about.
But of course you did not remember it or we were not aware that it can be used like this.
So PMI was actually used to prove some fact or some equation.
Okay.
So for example, let's say if you want to prove that okay some function okay is true for all n okay.
For all n belonging to natural number.
Right.
So let's say you have some function which is having some.
I would say expression.
And you want to prove that okay this function is true for all natural numbers.
So you can do that very easily using PMI okay.
So PMI actually gives you a framework using which if you perform these steps and you are able to I would
say uh properly uh just perform those steps particularly.
Right okay.
Then you can say using PMI that yes, this whole equation is true or this particular fact is true.
Now let us learn about them okay.
So the very first like PMI basically says that we can break any of these problem into three steps.
The very first is prove that f of zero or f of one is true.
So basically PMI is asking you to prove one base case okay, something of a base where it says that
okay.
You know that okay.
It is true.
The second and the most important step is actually assume f of k is true.
Okay.
So k is basically any natural number.
So you have to assume I will be focusing.
And I would say pressing you a lot on this exact word and this step because this is the most important
one.
I'm going to make so many diagrams for you to make sure that you get this particular point.
Assume okay, you have to assume that f of k is true for any k okay, which is less than n basically.
So we are going to see I'm going to show you an example now using step two right using this step two.
And we have step one as well.
So using the step two which where we assume that f of k is true, we can prove that our f of k plus
one is true.
And if you are able to do all these steps, if you are able to do all these steps properly, then using
the principle of PMI, you can say that yes, your equation of particular code is right.
Okay.
So let us of course I know that it will be still a little unclear and in the air.
So let me just try to help you to understand this a little bit better.
So we are going to prove this particular equation using.
So let's say we have some of n which we write something like this.
Right.
So sum of n n into n plus one by two.
Now how can we say that this is true or not.
Right.
So this is kind of one factor equation which we are saying that okay it is true for all natural numbers.
Right.
But how can we prove that.
So that is where now PMI will uh basically kick in.
So let us prove this.
Let us prove.
Using PMI.
Right.
Great.
So the very first thing okay.
So I'm going to just do the steps which I've told you just okay.
So that is something which we are going to follow.
And you will see that how it's going to help you to prove this particular thing.
The very first thing is base case.
Okay.
Uh, let us prove for f of zero or for that matter, we will prove both for f of zero and f of one.
Okay.
For f of zero.
Let us see what is the LHS.
LHS is going to be summation of zero, which I know is zero.
And my RHS right hand side.
and I know it's a little bit maths, but please be with me because this thing will help you to understand
a very important concept of recursion, which you will actually be very happy once you solve the question,
because it is not normally mentioned.
And that's why I think most of the students face the problem.
So the right hand side is also zero.
Now what this both effectively implies.
What these both effectively implies is that LHS is equals to RHS.
So I have proved this particular thing for one of the base case, or I have made sure that I am able
to prove this for f of zero, right.
In a very similar manner, if I just prove for f of one as well, what effectively I am doing is summation
of one.
I know that okay is just one, so it's going to be one RHS.
I have the formula so one into one plus one.
So I'm just putting in n in this particular formula.
Nothing else right.
So yeah one plus one by two.
And if I do this it is also going to be one.
So I have here also proved that LHS Is equal to RHS.
Hence, I have proved this particular thing for your f of zero and f of one.
That is the first step done.
Now let's move to the second step.
Okay.
Second step is actually very, very important.
And I would say rather the most important and the difficult most to uh, master when we will do ocean.
But yeah, for the time also just stay with me and assume you don't have to question this.
So assume don't question.
Right.
You just have to assume this.
Don't question this, please.
That f of k where k can be any natural number again is true.
So you have assumed that your f of k is true, which implies.
If you are assuming this, then you are assuming that f summation k okay is equals to sum of k.
Is equal to k into k plus one by two.
Now for a natural number.
I am assuming that this is true.
Okay, I have still not proved my this particular expression.
I have not proved that this is right.
I have assumed this and I am not going to question this.
And I am saying that this is right.
Now what?
PMI says that if you have these two things, if you have these two things and using these two things,
if you can prove.
Okay.
So now we need to prove that f of k plus one is true right.
So I have proved for a smaller problem which was my f of k like I have.
Sorry.
I have assumed for a smaller problem, which was my f of k, right?
Now I have to solve for the bigger problem which is k plus one.
Okay.
So let us solve this as well okay.
So what will become my k plus one if I do it like this.
Summation k plus one.
This is going to be something like sum of n.
So I am just filling fitting in the value of.
In the first I would say equation, which is going to be something like this k plus one into k plus
two divided by two.
Right.
So this is something which I'm going to just assume.
And this is just I've put k plus one here instead of n okay.
Now let us see.
Let us solve for LHS first.
Now my LHS is going to be something like this k plus one.
I can write this as k plus one plus summation k right.
So I can write summation five as five plus summation four.
In a similar way we are doing four factorial.
But yes, let us think in terms of sum.
This time I can write summation of ten like all the numbers in ten till ten plus summation n.
Now this is k plus one.
This I know this particular thing I know from two, right from step two.
I know I have assumed that this is true, so I do not have to question it.
I know that I can write it like this.
So this is where your last step was helping.
Okay, Uh, just one second.
I have to correct it.
It from two, I can get the value of this particular thing right.
So just let me remove this.
Yeah.
Great.
So k into k plus one by two.
I know that this is true.
PMI says that you have to assume in the second step you don't have to question this.
Now I can just multiply and divide this particular thing by two right.
So I can write this as k plus one into two divided by two.
It's one and the same thing and k into k plus one by two.
Now I can take k plus one by two common from this whole equation.
So this is going to become k plus one divided by two.
And it's going to be two and k.
So it's going to be k plus two.
And if you will see now this is exactly equal to RHS right.
So this is exactly equal to RHS because what was my RHS in this particular formula.
Exactly.
This thing.
So now what I can say now what I can say is.
Hence, by using principle of mathematical induction, we have proven that summation of n is equal to
n into n plus one by two, and that is valid for all n like for all n belonging to natural numbers.
So one, two, five, 510,000 everything.
It is true okay.
So yeah that is what we have done.
Now I know that this will be still a little bit confusing, but let us let me remove that confusion
as well.
Everyone.
So see.
Now let us go a little bit deeper and understand why this works.
Now let us go a little deep.
And understand the working right.
Understand.
How exactly it works.
See, what we have done is what we have done.
Is something like this right?
I have told you, like, you can think of this very intuitively in form of a building like I have told
you that, hey, in my building, this is the ground floor.
So I have given you the base.
Okay?
I have given you the base, and I have shown you the way that.
Okay, let's say I'm assuming right for a ninth floor.
Okay.
That I have assumed that.
Okay, I can be a ninth floor.
And I have shown you the way that you can take a single step, take a step from this ninth, from this
k to k plus one, okay.
So we know that we have the base.
We also know how to go from a step to another step.
Right.
That is what we have done in the uh like in the PMI in the next two steps.
So now I know the base okay.
And how to take a step as well.
So don't you think that now I can move forward.
So let's say now I have an idea now.
So I'm going to write this down as well.
So basically and just stay with me.
This all is going to make a lot of sense now.
So basically we know the base, right?
We know the base and how to take a step forward as well and how to take a step forward.
Which means that is we can keep on taking our steps, taking our steps.
Now, let me just help you to prove it a little bit more deep.
Okay.
So let's say I have proved already, let's say I know that okay, f of zero is true, right?
So I have proved this already in the previous example as well.
Now let's say my k okay.
So the k I can take as any number right.
So let's say k I am taking as zero okay k I am taking as zero.
And I am proving that f of zero.
And let me make it one so that it is helpful.
So you can think in terms of natural numbers.
So let us say I have taken f of one is equal to true.
Now I am taking my k also as one okay.
And I know that okay This is going to be true, right?
So f of one, I am assuming that this is going to be true as well.
Now, don't you think that using this thing you can prove for f of two, you can prove for f of two,
right?
Because you know f of one is true.
You have taken k, now you are just proving for k plus one, right?
So your F of two is true as well.
Now using this thing using that this f of two is true okay.
Let's let me now take my k is equal to two.
Don't you think I can prove for f of three.
Then I can prove for f of four.
And in a similar way in a similar fashion, I can keep on moving forward and actually go up the way
all the way till n, because I know taking a single step and proving everything, I can go all the way
up to N, and finally I can prove all these things right.
So this is the exact logic and thing on which recursion also works.
So let me just add a page.
And now let me give you the three steps on using which you can solve each and every question okay.
So in every recursion question In every recursion question.
We just have to.
Apply PMI.
Okay.
So we just have to apply PMI.
And this the steps will gonna make everything clear okay.
And PMI says that once you do this okay if you are doing this properly then your work is done.
So what were the three steps again.
The very first one okay.
Three steps.
The very first one was base case right.
So we have to just take a base case.
We have to say that okay this is the base case.
And I know this is going to be right.
Second I have to assume and I'm going to again be very pushy on this particular thing.
Assume you don't have to question that for.
So this time I'm taking my k as n minus one okay.
So I am assuming that for my k which is n minus one, which is nothing but my small problem.
Okay, I have to assume that this is true.
I have gotten my answer rightly.
How I don't care.
PMI says that you don't have to question this.
You have to just assume that, okay, you have gotten this.
Now, I know that this is going to take a lot of time, and that's why I'm going to do lots of questions
with you, because this was something which even I took a lot of mind and everything.
But yeah, you have you will get hold of it once we do two three questions.
Now using assumption.
In step two.
In step two and base case.
Basically just using both these points we can solve for bigger problem.
We can solve for bigger problem.
If you have done this work properly then PMI says that you don't have to worry if you have followed
these steps properly, you don't have to worry.
PMI says that you will get your answer.
Okay, so you don't actually have to worry on that.
Now we don't actually in a way we don't need to we don't need to draw, okay.
Those function calls for one, two, three.
Nothing.
We have to do function calls over and over again, over and over again.
Right.
So yeah, I hope this is clear.
Now I know that this is a little bit maths and things to wrap your head around, but now you're going
to see when we do the question.
And we are just going to do the questions now.
Right.
So the way I have explained you now you will see the magic okay.
And I know it's seeming a little bit magical, right.
That hey, I can just tell the base case and then I can just tell you what exactly is going to happen
for n minus one.
You can assume that and you can solve the whole question.
Okay.
So now let us see how we are going to solve the question by using all these principle.
So the question which we are going to do is finding Okay, two to the power n for a given n right for
a given n.
So this is just the quotient which you are going to do using recursion, right?
Now let us see exactly what is going to happen.
So how I can apply PMI to this understanding.
And again please see this video.
Again I know this is a little bit, uh, I would say tricky to, uh, wrap your head around.
You might be seeing this like a magic or what exactly happened.
If you will see this two three times when you solve some questions, which I am going to now do like
we are going to solve easily 510 quotients so that this understanding becomes clear to you.
Okay.
You will get hold of everything.
And again this question can very well be solved via iteration.
But we are going to use recursion.
Okay great.
So let me just define a function power two okay.
And let me take an n here.
And let's say I am finding the power two of n.
Okay.
So something like this I am doing.
Now I can just print this print power two of A fight for the timing.
Okay, now let me write my function.
Now let me write my function.
See, uh, the very first thing what PMI says is define your base case.
Now, I know that if n is equals to one, my answer is two, right?
So I particularly know this thing that, hey, when you are saying me to ask for find for one second.
Yeah.
One second everyone.
Yeah.
Cool.
So you are asking me to find for, uh, two to the power n and I know that, okay, for my base case,
when my n is equal to one, the answer is going to be two.
Right.
Pretty straightforward base case.
Now the next thing okay.
Next thing very very important.
Again the most important step you are going to find the small answer.
This small answer is going to be power two n minus one.
Now I don't care okay.
For this answer how this is going to get calculated.
As of now I don't care.
I'm going to first write my code and then I'm going to show you the exact thing.
That is not a problem.
But while writing code, you're not going to go deep.
You're not going to think that, okay.
How exactly are you going to get your answer?
You have to assume that, hey, for n minus one, you got your answer.
And this is the right answer which recursion has given you.
Now, if you have this answer, which is your right answer, can you find your answer?
I think you can if you have.
Okay.
So let me let me just show you as well that how we solve this problem.
So and can we write a recursion relation for this as well.
Pay attention everyone.
So this two to the power n I can very well write this.
I can very well write this as something like this.
Two into uh, just one second.
Yeah.
Two into two to the power n minus one.
So if I have this power, let's say two n.
So I'm writing this in just a maths function.
Then we can write it something like this.
Write power two n minus one okay.
So this is the base and this is the power.
Now this overall is again a recurrence relation.
Everyone we are using the same function.
Don't you think this is a recurrence relation.
Everyone.
So we are using the same power function In this particular code.
So this becomes a recurrence relation which I can use further.
And once I have gotten this my recursion function or recurrence relation.
So this is known as recursion function or relation.
Okay.
Recurrence relation.
So if anyone asks you to write a recurrence relation that is something which you have to write relation
okay.
Now using this knowledge using this knowledge, once I have created this particular thing, what I have
to just do is I have solved for my base case.
So this is my base case, right.
Base case one.
This is my second step where I assume okay.
So it is known as step two.
This is known as actually induction hypothesis.
This is known as induction hypothesis I think I have mentioned this here as well.
So one second.
Yeah.
So it is written here.
So this step is known as induction hypothesis where I just assume okay I don't question it I just assume
this.
Now this is induction hypothesis.
Now once I have these two steps, in the third step, I can just use this thing and find my answer.
And the principle of PMI says principal of PMI says that you don't have to worry.
Your answer is going to be right.
If you have done your work properly, if you have done this particular thing properly, and if you have
used this particular thing.
So see, I've used this small answer that is something which we used in some question as well.
Then PMI says that you don't have to worry, you have done properly and you don't need to actually work
on that.
But I am still going to show you because see, first you are going to write the code and then you're
going to actually draw everything.
You are not going to initially draw these functions, because then you will keep on drawing these functions
if given with the question.
Now pay attention.
What is exactly going to happen?
The very first call I'm going to make for n is equal to five.
My power function.
It's going to check in line two and three.
But at line five at line five right.
It's going to make it's going to make a call to my function with n is equal to four.
Now again what's going to happen at line five.
This is going to make a call to n is equal to three.
This is going to make a call to n is equal to two.
And finally a call to n is equal to one is going to get made.
Now for n is equal to one as you can see here.
As we can see here I am returning two I am returning two.
Now once I got my small answer in this n is equal to two.
I'm going to just multiply it by two and return my answer.
So I'm going to return four.
Similarly this three it's waiting at the line five as of now.
But once it gets the answer it's going to find its answer and return it.
Similarly, when my four, which was also waiting at line five, it gets his answer.
It's going to return at line answer as 16.
And finally the n is equal to five.
It's going to return the answer as 32.
So this is the exact same thing which is happening behind the curtains.
But again you don't have to do that before writing the code, you have to use PMI to write your recursion
code, and if you do this, I can assure you you will never, ever face any problem in any of the recursion
code we are going to do a solve.
I would say the difficult test of the question.
The most difficult question is when and you will see that okay, we are not facing any problem.
Yes, it's a little bit, uh, not, I would say complex, tricky and magical to wrap your head around,
but it works and I can show you that as well.
See, it gives you the answer as well.
So while writing the code, I didn't I just use PMI.
And because I have I know that okay, recursion by in the back end is using the PMI principle only.
It is working absolutely fine.
Let us now see this quickly.
Just once I will show you this code quickly here as well.
So again same thing happen.
Power two gets defined.
We are calling it for five.
Five is going to check if it's one.
It's not one.
So it's going to call for for for going to call for three.
Each and every one of these functions are still in the memory.
They are waiting at line number five.
It's going to call for two.
Then finally the call for one is going to get made now while writing the code, I didn't think of anything
right.
So in my in while writing the code, I just follow the principle of PMI.
And that is something which you also have to do.
So if you have not, if n is equals to one, right.
That is where I was returning to.
So return value is true.
Let us go back.
Now this power two okay.
For n is equals to two.
Got his answer is small.
Answer two it's going to find its answer.
Going to return that answer.
Then it's going to find it.
This particular way then is equals to three.
Going to find it.
Answer and return the answer.
Power two with n is equals to four.
Going to get it small answer find its answer 16 and going to return the answer.
Finally the code which we called okay.
It also got its answer.
It's going to find the answer and return it.
And finally we got our answer as 32.
Now I have shown you this three times, this working and everything, and I hope you know the reason
because it will be a lot more clear to you.
But I have also shown you how you have to actually write this code, right.
So I have not actually drawn this before writing the code because that's what PMI help us to do.
And yes, it's magical if you understand it.
And I hope that I have done a good job in explaining you this, because now we are going to solve lots
of questions, and in each and every question you will understand that exactly how using the PMI, we
will be able to write the code for recursion and we don't have to worry on anything.
Okay, so great everyone.
Now in the next few classes we are just going to solve lots of questions of recursion and master it.
Please make sure that you see these for like three four videos which in which I have explained again
once because that is going to help you a lot.
And recursion.
As I said in the starting, it's a little tricky to understand, but with this overall framework mindset,
you will be able to actually solve each and every question of recursion.
And that I can assure you, because that is something which even I took a month like to master and understand.
And after that I like kind of wrote and explained you in that way only so that you don't face any problem.
Okay, cool then everyone.
So we will meet in the next class and we are going to solve lots of questions.
So then we will see that exactly what happens and how recursion is so magical in solving so many of
these questions.
And we will master recursion.
Okay, cool.
Then everyone, let's meet in the next class.
Thank you.