Hello all and welcome back.
So in this video we are going to continue our discussion on understanding recursion.
And we are going to understand that with the example of factorial of a number.
Now, I hope you have watched the last two videos, because there will be a lot more important in properly
understanding the recursion, so that you never face any problem in that.
So now let's get started.
The very first thing which I would like to define is how a factorial of a number is actually calculated.
Right?
So if you have to find factorial of a number n, it is actually written as n with the exclamation mark.
So that's a symbol for factorial.
And we write it something like this.
Right.
So we keep on multiplying the number and one less.
Then we subtract two.
And we keep on going till we reach one.
And that is how we say that okay we have got the factorial of a number.
Now the next thing which I want actually to think of based on the discussion which I discussed in the
last class, is can I make it?
Can I make this problem a problem where the solution actually depend on something of a same problem,
but with a smaller input, right?
So I will repeat once again what I tried.
What I'm trying to do is I want to make finding out the factorial as a problem where I can solve the
same problem, but with a smaller input, right?
So I think that's that that is actually doable if you see these numbers.
Right.
If you see all these numbers, I can actually write it something like this.
So my n minus one factorial like if in this particular formula I change n with n minus one, then I
get the formula for n minus one factorial.
So in that note, what effectively my n factorial boils down to is n into n minus one factorial, right?
So pretty intuitive.
Pretty easy to understand.
But I wanted to make sure that you understand that with the respect of a particular understanding of
recursion.
So I saw that yes, my problem of a factorial can actually be written in a way where I can solve the
same.
Solve this problem by solving a same similar problem.
Right?
So this is something which is called as recurrence relation as well.
Now we are going to talk a lot about it.
We are going to write and find it for lots of, I would say, questions as well, because that is very
much important.
What effectively is happening here is that we have actually made our problem.
So I can now write this effectively, as if I want to find factorial of a number.
I am very good to find the factorial of a number.
If you give me the factorial of a number which is one less than the current number right now, moving
forward with the same mindset, what I can effectively do is I can write factorial of my n minus one,
something like this, n minus one into n minus two and all the way to one.
Now if I move forward, I can similarly write this into n minus two factorial.
So we saw that yes, this problem is something where we can solve this problem by making this problem
a step smaller.
Right.
So now let us try to code this thing.
Let us try to code this thing and actually see if we can solve this via recursion, because we have
gotten a recursion relation where we are able to satisfy this particular definition.
Right.
So now let me code this.
So let's say we have a factorial as a function which takes in a number.
And what effectively I am doing is I am returning n into factorial.
I'm calling this again.
So yes, it's a case of recursion.
And let me now try to find the factorial of five.
Right.
So let me run this.
Now many of you might be thinking something and yes, that's going to happen.
And I got the same error right.
So it is just showing that this line repeated 996 more times.
Recursion error maximum recursion depth exceeded.
Now here I would also like to just show you one thing from Google directly.
We can see that why Python has maximum recursion depth, right?
So just let me remove this.
And yeah this should answer maximum recursion limit.
Maybe we can find.
Yes.
So the limit actually prevents infinite recursion from causing an overflow of the sea stack and crashing
Python.
So if you have seen the last video there, I also explained you about the stack memory, right?
So Python actually just uses this internally limit on the maximum recursion which you can call.
And that is actually done to avoid the overflow of your stack memory.
Right.
So as we all know Python is written on top of C.
Now these things becomes important from a view point of perspective that because if you will be writing
the same code in C or Java, then you will get some segmentation error or memory exceeded error.
So that is very important to understand in Python.
In Python you can effectively change this uh limit.
So if you see import sis and I write sis get recursion limit.
And let me just comment this code.
And if I run this okay.
Sorry I have to print this as well.
So yeah.
Which one is never closed up.
Recursion limit okay I think it is not updated.
Yeah.
So it's giving me 1000 right.
And I think that's the reason effectively why we saw when we run this that this line is repeated 906
times.
So some four five basically will be kept.
But yeah, if I so in a similar way, because I can see this recursion limit, I can set this recursion
limit as well.
Okay.
So maybe let's say if I set it just for 100 and now I run it.
Now you will see this line is repeated 96 more times.
So for maybe it is keeping or using internally or for something okay.
But you are able to see okay, it is not like that.
So we are seeing this for and it is repeated 96 more times.
Right.
So that is how this recursion limit is getting used.
Python internally sets it and even allow you to set it so that okay, in case if you encounter a like
a code like the one which you have written where this limit exceeded, it can prevent that stack overflow
case, right?
So this thing is very important to understand.
And now is the right time to understand.
Because going forward you are going to write lots of these functions on recursion.
Right.
So yes we saw all these things that exactly what is happening.
Just one thing I would like you to show again so that all of you can understand.
Though I'm pretty sure based on our previous understanding previous working, these will be a lot clearer,
right?
So let us see exactly what is happening.
So I define this method and actually let me just write this code a little bit easier so that all of
you understand what we can do is I can define a small or I would say small answer.
Right.
Small answer I can just find by factorial n minus one.
Then I can find my answer that is going to be answer into small answer.
So I am just dividing it into variables.
And then I can return the answer right.
So same thing.
Just I made sure that I am defining the variables for this.
And we see that yes, this is getting repeated 96 more times.
So because you have set it 100 this time, so it is just getting called for 100.
Now you can make it ten as well.
But the problem is that it is a very less limit.
Right.
We can have codes where if let's say I find the factorial of ten.
So of course it will be making ten calls and we don't want to exceed them.
Right.
So this thing is very much something which is not aware.
People are students are not aware.
So make sure that you understand this very nicely.
Now let me now run this code and show you exactly what will be happening, right?
Many of you will be able to understand it based on our last two classes and the discussion of functions
which we had there.
But yes, I still want to make sure that I actually put this thing in your mind.
That record this functions can get call itself.
And yes, what exactly is happening, how things are in the memory.
So n is equal to five, n is equal to four.
So see at every of the second line in all of these factorial function it is calling a same function
but with a less output like with a smaller problem.
So in a similar way, what is happening is that I am just trying to call.
I know that factorial of one is equal to one, right?
I know this thing.
But again, this is still going to go to zero, and this is still going to go to minus one, and it's
still going to go to two three.
And it's going to repeat right.
That's why it is saying stop.
Since stack has 30 functions in it.
Maybe the limit here is 30.
And your code may have infinite recursion.
So it is also giving us an idea that, hey, your code seems to have an infinite recursion, right?
So now let us try.
Now let us try to solve the same thing.
Many of you might have guessed this thing right?
So if my n equal equals to one, then I can just return one.
So here effectively what I have done is I have added a base case or base limit on my recursion code.
What this help is when my n is equals to one.
It's very analogous to the code which he wrote here, where when we reach this thing we are not calling
anything and print num one, we are not calling anything.
So in a very similar way, we have just made sure that we are able to stop these calls.
And this is known as a base case.
Right?
So now when I will run this function you will get the answer.
So okay I think we have not printed it.
So just one second and let me just print this lines.
So now when you get this I get the answer as 120, which I think is the answer for five factorial.
As you can see, five factorial is in fact 120, right.
So I am able to get the right answer.
Now, just let me quickly make this understanding a lot more clear to you, like exactly what would
have happened.
And the reason for that is I want to make sure that you understand each and every step.
So what would have happened is first of all, with n is equal to five, we would have called a function
which is factorial function at line number 12.
Like this.
Lines are very important as well.
So I'm going to write them separately at line number 12.
This would have called for n is equals to four.
Again this function it's going to check for n is equal to one.
And they are not.
So it's going to call again for at line number 12 of this particular function it's going to call for
n is equals to three.
Then n is equals to two going to get called.
And finally of course we are going to call n is equals to one.
Now all of these are going to wait at line number 12 and wait for the execution to get completed.
But for n is equals to one.
We actually have written a case.
And this case is something which is going to get used.
And this is known as a base case.
Now this base case effectively what it does is it actually base case is a case where we don't have to
make further function calls.
Right.
So n is equal to one.
Now I know that because the answer is one it's going to get returned.
And now this execution of for n is equal to two is going to get started.
It knows that small answer I got somewhere from here is one.
So it's going to calculate its answer which is going to be two.
So its answer is going to be two right.
In a similar way it's going to return its answer which is two.
So I can just write it like this.
It got answer as two or sorry small answer as two.
And answer is something which it's going to find which is going to be three into two, which is going
to be six, and it's going to return six.
In a similar way, this essay got a small answer as six answer is going to be four into six, which
is going to be 24, and it's going to return 24.
And small answer here is not 24.
It finds its answer, which is going to be five into 24, which effectively is 120.
And finally, here we are going to get answer as 120.
So this is the exact whole flow which is happening.
I hope all of you are understanding clearing like clear with this thing.
Uh, I will I'm going to run this on Python tutorial as well.
But again, just one more thing I like to do.
If you all are facing some problem in that, and that I think will make it a lot more clear.
So what I can do is in a similar way I can make functions like this.
Right.
So factorial for it's gonna.
So let me just copy this.
Yeah.
So now this is actually becoming that same problem right.
Which we saw in the last class.
Now the reason I'm showing you like this is because it's going to make your understanding a lot more
clear that what in what is like happening inside.
Right.
What exactly is happening inside.
So I'm just calling now two.
But the factorial one like this is not going to call anything.
This is going to just return one.
And now if you will see like this is exactly what happened in the back end.
Right.
This is exactly what is happening in the back end where these functions like these are getting created,
right?
So now if I will run this, I'm again going to get the same answer.
But now I think you will all be able to very easily visualize that what exactly happened.
Right.
So just let me call factorial one here and now.
This code should also work as fine.
And we are getting the answer as 120.
So let me show you.
Let me show you the overall I would say first this overall working.
Or just a second.
Yeah.
So we can see this is working.
See what exactly is happening.
And just always remember okay I think it doesn't have a import library so no worries we can remove this.
I think it must not be having that.
Or just make sure that you understand this with the point of recursion okay.
So see what's happening.
First all these functions are going to get defined in your I would say frame and the global frame.
Now when I call for factorial five, factorial five is going to get called at this line number four
it's going to call factorial four.
Now in the recursion use case, of course it was making a same instance of factorial function only.
But now to explain you very much properly, I have defined and made another function.
So factorial four is going to go.
But you have to understand one thing very, very nicely that this function of factorial, it's still
waiting.
It's still waiting in the memory at this line number four.
And it's not gonna get, I would say deleted or gonna get, uh, executed till it gets its answer right
in a very much similar way for it's going to wait at line number nine.
Then it's calling three, which is going to wait at line number 14.
Then we are going to go to two.
It's going to call factorial one at line number 19.
And because one was kind of a base case where we knew the answer, we can just return one.
Now once this returns one okay.
And you're going to see one more thing here, which is very important that if I make it inverted down
something like this is happening.
So this is why it is known as stack.
So we are going to study about stack data structure as a standalone as well.
But I hope you understand that what is happening.
Right.
So the functions are coming in this order.
Right.
So five was the first function to come, then four, then three, then two, and then one.
Now, because one gets resolved, it's going to get out, right.
So let us see this as well.
So one is going to return the answer as one.
And it's going to get deleted right.
So this is now get out of this particular code.
So this thing is basically now deleted.
Now two got its answer.
And at 29 it's going to continue with its execution.
And it's going to get the answer as two.
It's going to return it.
Similarly it's going to also get removed from the stack memory in a very similar way.
And you can see that all of these are waiting.
Right.
So three is going to get its answer and going to return it, four is again going to get its answer and
going to return it.
And finally we are coming to five.
Okay.
Finally we are coming to five.
Just that in the other code you are not able to see these codes, right?
So that's why I made sure to make them separately, so that your visualization and your understanding
in the back of your mind is a very is very clear.
Now, when I finally find the factorial right, I am actually able to see that okay, the answer is
120.
And that's how it is returning me 120 as answer.
So return value is 120, which we are finally printing and we get our answer right.
So again, just to I would say show you again and again I'm going to make it like this.
So let me move all these lines.
And now I think everything will be a lot more clear to you because now when I show you this overall
working, you all will be able to make sense of it.
See, now, just one thing has changed.
Uh.
One second.
Okay, I have to edit this code and we have to call factorial.
We are using recursion this time.
So yeah.
Now just one thing.
I have changed everyone, which is we have just a factorial function.
Right.
So this is 24321.
All of them are deleted.
But we have understood that yes they are going to get defined.
So see factorial with n is equal to five.
Get defined.
It's going to check if it is one right.
It is not one.
So it's going to go and it's going to call small answer.
So earlier it was calling factorial four.
But now the same function is just getting called with a factorial function with a value of four for
getting called, then three getting called, then two getting called and finally one is going to get
called.
But the thing with one is that because we have mentioned that if our n is equals to one right, it's
going to return one.
So again, the same thing is happening here as well.
And this is very important to understand.
That's why I'm drawing it so many times and showing you the exact execution.
Because I feel when you are learning recursion for the first time these all helps a lot.
Like this.
Visual tools helps a lot.
Now finally, because we know the answer for one it's going to get returned.
It's going to return you the answer as one.
This is going to calculate this answer and going to return two.
Going to return two.
Yes.
So this is going to return six.
Let us see this happening as well.
So it's return one right now this factorial two.
It got this answer as small answer.
And you can understand now.
Right.
So we just define these functions separately in the last example where there were 34321.
And right.
So now it's just going to return its answer as two.
Going forward it's going to return this answer as six factorial with n four is going to return its answer
as 24.
And finally factorial with five.
The direct function which we called.
But I think now you're understanding that okay, how in the back end these functions are getting, uh,
I would say created how they are getting removed, in which order they are coming in, in which order
they are coming out.
All of this you are able to visualize.
And finally, I will be returning my answer with 20.
And because I called this here, this is where my flow gonna come back.
Okay.
So yeah I'm going to get my answer is 20.
So with that okay.
With that I hope all of us are clear with the with that, I hope all of us are clear that how overall
the use case or the recursion is working in the behind.
Right.
So we did solve and I think we are now able to see and uh, basically just check again everything,
all these things which we learned that about functions, about recursion overall.
Okay.
Few things we saw and which I think is also clear that how recursion was facing a maximum length exceeded
error.
Right.
So recursion at one point recursion was giving us.
Maximum length.
Maximum depth exceeded I think.
Right.
So maximum depth exceeded.
Now the reason for that I have already explained you that because we didn't have base case.
So the all the working and everything was going as forward.
Okay.
So we have to make sure.
Okay.
So I'm going to write this as well.
We have to.
Make sure.
That recursion stops somewhere.
Stops somewhere.
And don't keep on going till infinity.
Right.
And for that we have seen that exactly what we do.
We add a base case.
So I am writing all this thing down so that you have actually this in your mind, right.
Because these are going to a lot useful to you.
Right.
When you're going to write these code for recursion, these all things are going to be a lot useful
to you.
Now just one thing.
If you have seen as of now and you must have realized that, hey, what if tomorrow we have to find
out this for n is equals to ten?
Are we going to draw like this?
Ten boxes?
Am I going to draw the whole sequence and everything?
Well of course that is not feasible.
And the answer for that is of course no.
So now.
We will not be making these functions call.
Okay.
We will not be making.
These function calls.
And basically finding the small answer and everything.
We are not going to find the small answer and everything.
And even thinking of recursion this deep even think of recursion.
This deep it was important so that I can clear your mind set clear the, I would say, confusion which
many students face.
But we don't have to do this every time.
Yes, I will still be doing this with all of you in the first 1015 questions I solve so that your understanding
is clear.
But when you solve the question and once you become comfortable, you don't have to draw any of these.
And the reason for this, you will understand with the underlying principle on which our underlying
maths on which recursion is based.
Because that is again, very, very important.
And that is actually something known as PMI principle of mathematical induction.
Okay.
So that's the overall I would say uh on which your maths is based, maths of recursion is based.
So we want to learn about that.
Now that is going to help us to actually understand that, how uh, we don't have to draw any of these
things.
Right.
How we can assume the answer and everything.
So let's meet in the next class, and I'm going to make it clear.
Just make sure that you understand and see this class again.
If you have any doubt.
I have again drawn things 4 or 5 times so that you don't face any error and you are able to visualize
these things.
Visualizing and having that in your mind is very, very important.
Okay.
So yeah, let's meet in the next class and we are going to learn about PMI.
Thank you.