Hello everyone.
So welcome back.
Now let us continue our discussion on recursion and let us try to solve the question which I gave to
you in the last class.
Now the question, as we already know, is something based on the way we understood PMI.
But yeah, I'm going to solve this question for you.
Draw everything and actually do it the way you should be solving first 2025 questions in your recursion
journey.
Okay, so the question says that I have to find sum of all natural numbers up to a given number n.
Now, if I have to write, what exactly that would mean is if I have to write sum of n, that would
be something like n plus n minus one, n minus two, and all the way to one.
If I just see this particular particular equation properly, then I can say that this can be reduced
to something like sum of n minus one.
Right.
So just this whole I would say expression is nothing but sum of n minus one natural numbers.
Now you will see that okay I have actually formed a recurrence relation or recurrence function.
Right.
So this is a recurrence function which I know which I can use.
Now let us talk about what exactly is Recursion tree.
And that then is when I would say we will write the code for this particular problem.
So recursion tree is actually the same I would say function call which we used to make.
So let's say if you are given a particular n right, how this is going to solve the problem is it's
going to call to n minus one.
Then this is going to call to n minus two and all the way till one.
This whole thing is going to basically get reduced.
We are going to see an example of this.
So let's say if it is for five it's going to call for four.
It's going to call for three.
This particular we are going to call for two.
And then we are going to call for one inch the end.
Now we are taking one as our base case.
So that should be fine.
Like we have to draw till the base case, or we have to just at least tell that okay.
So for example I have drawn dots here till the base case.
Now if you will see here I will just can actually solve the question using this.
So I can just show you that hey one is getting written here.
This is going to let's say return three.
Now exactly what is going to happen that of course, we are not going to do.
But in the context of Recursion Tree, you should be having an idea of this.
Like this is exactly what Recursion Tree is, right?
So now let us try to solve this question.
And I'm going to solve this question with all the, I would say, principles of PMI only because that's
what exactly on I would say a recursion is based.
So the very first is the base case.
If my n is one, I know that my answer is going to be one only.
Right.
So this is just my base case and I can write it as step one.
Second part I have to write my small answer or small value or small output.
Now I know that okay, if I have to find for n minus one, right?
So if I have this recurrence relation and it is going to help me.
So this is actually what my small output, small answer and everything is if I use this then you can
see that I can just directly call for that.
And I have to assume that I will get my answer.
I will get my answer.
So even if, let's say you are calling it directly for 500, I have to just assume that, okay, I am
getting my answer.
And if I am able to now using this particular answer.
Find my answer properly.
There is nothing which I should worry about.
Principle of mathematical induction says that I will be able to get my answer, and there is nothing
wrong which I am doing.
And now I am going to return the answer as well.
Okay, so for the time being, let us just do it for five, because for 500 at least, I will also will
not be able to draw that.
So now let us see that everyone.
So pay attention.
What exactly is happening here is something like this.
We have actually now called this particular code.
Okay.
So I am just writing this sum as the function we call it for n is equal to five.
It checked if n is equal to one or not.
And it actually then call on line number five okay.
So this line number is very very important as well.
Let me write this in green on line number five.
It wrote it basically called for n is equal to four.
So the function for n is equal to five is still waiting in the stack.
It is still like hey get me the answer.
And then only I am going to get resolved.
This is going to again going to call for at line five.
It's going to be for n is equal to three.
Then we can call for n is equal to two.
And finally at n is equal to one.
So same function is going to get called.
So again if you will see the steps which I have followed, I have not drawn this earlier.
First I have written my code and that is something which I want you to all to follow as well, because
the reason I have taught you PMI is because if you draw this earlier without, I would say without writing
your code, you will never be able to write your code.
You will always get, I would say, uh, fixated or confused in this particular, uh, full functioning
or working.
And that is something which I don't want.
And you're going to see that how fabulous this overall technique in future.
Difficult question also going to help you.
So again this is the five line.
This is the fifth line of this which is waiting.
This particular code on line number three returns you with the value of one.
Right this.
See that.
Hey, I have gotten my small answer as one and let me calculate and add and get my answer, which is
going to be three.
Similarly, this three is going to return six because three plus three is six.
This n is equal to four is going to get its small answer as six.
And answer is now going to be uh, four plus six, which is going to be ten.
And finally I got my small answer ten.
I can return 15 as my answer, which I should get here.
And in a similar way for ten.
Also, we can get the same answer like for ten.
Also, the working is going to be the same, but you don't have to write it.
That's the beauty that I would say the magic of PMI and recursion.
Right.
So let us see this.
Everyone once let me just run it and you see that okay.
We are getting 15 and 55 now just to show you one more time to like have all your doubts clear.
I'm going to just show you again in Python tutor as well.
Again, this is very important so that you know, each and every thing is clear.
Like when I was learning recursion, of course I didn't learn that way.
So I have to face a lot of problem.
That is something which I don't want all of you to face.
Right.
So let us start the working.
Yes, this function is going to get defined.
I'm going to write this function for n is equal to five.
Like I'm calling this function for n is equal to five.
It's going to check it is not the case.
It's going to call for 432 and then one okay.
Now if you will see one we have the answer.
So it's going to return with one as the value in my two.
Now small answer is one.
And my answer, which I am going to calculate, is going to be three.
Now with three as an answer, I can return.
And again I can just calculate all these things.
Answer is going to be six.
Answer is going to be ten.
Answer is going to be 15.
And finally I get my answer as 15.
This is just one thing which I would like you to all to pay heed to.
See if I just find for 1000.
Right.
And let's say in many questions it can happen that you might have to increase the recursion limit sometime.
So this is an easy code.
Well enough easy code.
If someone has set recursion limit, let's say to 500.
In some I would say environment or in some particular leetcode or some other case, you might have to
increase that, because if I'm going to run it, it's going to give me the error because it's saying
maximum recursion depth exceeded.
But we know that, okay, that's not the case.
So maybe we can send it to 5000 normally.
Again 2000 is the acceptable limit.
But yes now we can get the answer right.
So we are able to get an answer.
So again like nothing to I would say very often this will not be the case.
Many platforms and everyone they have the recursion limit which is in I would say which is where your
code will run.
But yes, this is something because many times it can happen that if somewhere this code is being run
okay and your recursion is going a lot deep, so you might have to set this recursion limit as well
in Python specifically.
Okay, so I've already explained you on this set and get recursion limit.
Again something to be known if you are specifically coding in Python in C plus plus Java, that is not
the case, so should be fine.
And again if I am running this, this is going to be fine.
Now I hope all of you have seen that exactly how we have written this code.
Uh, what are the steps I have followed, how I have made this recursion relation, and how I have drawn
this recursion tree as well.
So I hope this is all clear.
Now, in the next class we are going to do some more questions.
And with this basic question your understanding is going to get crystal clear.
And once that is done, then we are going to move to some advanced level questions where we are going
to use arrays and a list or arrays and strings as well in our recursion code.
Okay, so cool everyone.
Thanks a lot.
Uh, I hope everyone is able to understand recursion.
Okay, please make sure that you just see this class again.
Uh, try to write the code first yourself and just follow all the steps which I have told you.
And you will never face any problem in recursion.
Okay.
Thank you everyone.
So let's meet in the next class.
Thank you.