Hi everyone.
So in this lecture with a strategic vision.
Okay so recursion is one of my favorite topic.
The best part of the equation is we can easily code the most complicated problems.
Okay recursion is very important topic because going forward in many structure we use recursion only.
Okay so we have to do recursion properly.
Otherwise we may face a lot of problems.
Okay so what is recursion.
What is the definition of recursion.
So recursion is when a function is calling itself.
Okay.
The definition of recursion is when a function is calling itself so function calling itself.
Okay so this is a recursion.
Okay so till now what we have seen I have a function mean main is calling a function a function a is
calling an other function b and so on.
Okay.
But here in the equation what I am trying to say here is a function will call itself that is we have
a function mean main function is calling a function a function a is a green calling function.
And so on.
Okay.
So it is a little weird when function e is calling function itself.
Okay.
Now let's try to think in a different manner.
Okay when we will use recursion so we will use recursion we will use recursion whenever the solution
of a problem depends upon the solution of a smaller problem.
Okay let us take an example.
So suppose I want to find an factorial.
Okay we want to find out what is in factorial.
So what we will do.
Can we write like an factorial is this is n and minus 1 and minus 2 and so on.
Kelvin Okay so can I write this line.
Can I write this part in an other way.
Can I write it like an factorial is and make the play and minus one factorial okay.
We can write it like this way.
Now suppose I have a function factorial Okay so I have a factorial function.
I will give it n and it will give me an factorial.
Okay so factorial off and it is.
Same as can I write like this and multiply factorial function and minus 1.
Okay.
So this is the function name fact is the function name.
Okay so this function takes I indigenous argument and it will have done me it will give me an factorial
factorial often as nothing but and multiply factorial of and minus one.
Okay so here we can see a function.
The fact function is calling the fact function but with a smaller input.
Okay.
So then we will use recursion when a problem depends upon the problem of the same nature but with a
smaller input size I am repeating myself we will use it caution when a problem depends on a problem
of the same nature but with the smaller input size okay.
So here we can see I have a problem.
I want to find then factorial.
It depends upon the.
It depends upon a smaller problem of the same nature.
Nature is same but with a smaller input sites okay.
Now what we are trying to do here is so we are trying to divide the problem so I have a big problem.
I have a big problem.
I will divide.
I will convert the problem into smaller problem.
I will again convert it into a smaller problem.
I will again convert it to a smaller problem and it will go on.
Okay so finally our problem will become very very small.
Okay.
So we are reducing the size of our problem.
Okay our problem size is being reduced.
Okay.
We can see here our problem now our problem becomes smaller.
Okay.
So recursion what occasion will do I have a big problem.
I will convert the big problem into smaller problem.
I will again convert the smaller problem in to smaller problem.
Again the smaller problem will be converted into smaller problem.
And so on okay.
Now let us try to see a thing called We Will tried to solve the same problem.
So let us take the value of an input from the user.
Okay so let's say I have a function fact.
So this function effectively done me the answer.
So I have this fact function.
I will give it n factory function and it will be done with the answer.
And let us try to predict the end factorial okay.
Now what we have discussed.
So what we have done type of the function it will be in digit.
Then it would function is fact and it will take a and b as argument holds factorial.
We have to conclude OK so what is the meaning of the equation.
What do we do.
We will find out we will convert the big problem into smaller problem so in small answer I'm calling
the function factorial and I will give and minus one.
OK.
So now at line number five.
I know the factory I live in minus one.
So what is the factory.
Often it will be what I will do I just have to return and make to play small said okay.
So what I'm trying to do here is I want to conclude the factorial often so at line number five.
What I'm doing.
I'm calculating the factorial of and minus 1.
Okay.
What this fact function will do this fact function takes an integer and it returns and in digit which
is the fact all of them but so this fact photo really will give me and minus one factory.
Okay.
And they're dead minus one factory is stored in a small answer.
And finally either done and multiply and minus one factory.
Okay now let us try to add another code and let us see what will happen.
Okay.
Now it is waiting for us to give input.
Let's say I want to calculate for the factory.
Okay so forth and that.
So what will happen what is happening here is basically we are getting segmentation fault in a finite
loop.
Okay so this is in finite loop we are getting segmentation for it.
Now let us try to brighten our code.
What is happening.
Okay let's try to drive it another good.
Okay.
So what is happening here is.
So I have this function mean I have this function when it is calling the function factorial often.
Okay so Maiden is calling fact and led to the values food and is food.
Okay so and is food now what is happening here is this factory function is again calling the factory
function.
So it is calling a factorial function but the value of an S T.
So the value of land is three.
We can understand it this in a different way but actually it doesn't happen.
Okay so let's try to understand it in a different manner.
So I have mean no men is calling a function factorial okay and the value of these food okay now at this
line what is happening here is let's suppose we have another instance of defect bowl function okay we
have another instance of the actual function and this is calling the factory but the value of this tree
you can see here and minus one.
Okay.
So this new instance is created you can assume that but it doesn't happen okay.
So now what is happening it is.
So what will happen.
This fact function it will call fact to again the value of and this to here.
Now what I want to say here is we know the local variables of one function is different from the local
variables of another function.
Okay so this end here the value of this for it and it had the value of industry.
So this end and this end they both are different.
Okay they are different.
Okay why different because we know the local variables of one function is different on the local variable
itself another function these are two different functions.
Okay two instances.
So this n and this end they both are different now what will happen this will call fact to when know
the value of and becomes one.
So what is happening here is as soon as we entered this function we are calling and a function.
Okay so now this fact when it will call fact to zero.
So the value of n is zero then it will call fact minus 1.
It will call effect minus 2 and so on.
Okay.
So basically it is we are doing in finite cause okay.
We are doing infinite cores.
So this is infinite loop this is infinite loop.
So we are getting segmentation for.
Okay.
So why we are getting segmentation fault.
So what is happening here is when I reach this line all these four functions when I am here all these
four functions are waiting for the factorial one function to compute its work.
Okay all are waiting all have the copies off and now it is taking some memory.
Okay.
This is taking some memory this is taking some memory it is taking some memory it is taking some memory.
Okay so what will happen.
We are we are doing infinite cores so at some time it will not be able the program will not be able
to create more memory and we will get segmentation fault.
Okay so when Irish fact minus two.
What will happen.
All these functions are waiting for the effect minus to function to compute its work.
Okay so everything will take memory they are taking small small memories but we are doing in finite
cores.
So had some time what will happen.
We will get out of memory.
Okay.
We will not be able to create more memory and we will get segmentation fault due to in finite cores
Okay so while there are finite calls because we started at an equals four then three two one zero.
So I deliver to happen.
We should stop at zero or we should stop at one.
Okay but here we are making in calls.
Okay.
Ideally we should stop at zero or one but we are making here in finite calls.
I can prove it also.
So how will I prove it.
What I will do.
As soon as I entered this function I will print the value of an okay I will print the value often.
Now let us try to run this file.
Now let's see the value of an is food.
And as soon as we will print ended so you can see here these are the values of n..
Okay so these are all the values of these main them but of course I am trying to make here okay.
So we are making many calls but we could not get our answer.
Finally we will get the segmentation fault due to the lack of memory.
Okay so we are making many many calls.
I don't know where it will stop okay.
It will stop when we get out of memory and we will get segmentation fault due to lack of memory.
Okay.
It is making these main number of calls and it is trying to find Don center this trying to find the
Ford factor.
Okay so at this moment what is happening here is we have due to lack of memory.
We are getting this segmentation forward.
Okay now let's call it up.
I am not able to call it more so what I have done here is.
So this is the same code you can see here.
This is the same code I have written this code on idea on and now let's say the input is food and we
will try to end the file we will try in the code.
Okay so you can see the output we are getting run by method where runtime error because of infinite
loop.
Okay.
Now you can see here this is the output for 3 2 1 0 and then minus one minus two minus three and so
on.
Okay.
You can scroll to the bottom and you can see you do a self okay.
So for 2 to 1 and then 0 minus one minus 2.
So ideally what should happen.
Ideally our program should stop at some moment okay.
Our program should stop at some moment now Vader should stop
okay.
So what is happening here is factorial for function.
This is calling factorial 3.
It is calling factorial 2.
It is calling factorial when it is calling.
Let's say factorial zero okay.
Now it is calling factorial minus 1.
Now according to mean there is no need of this call.
Why.
Because this is very trivial problem.
Okay.
What is 0 factorial 0 vector Lisbon.
So I already know the answer of zero factorial so why to make the call to minus 1.
Okay so what do we do.
Factorial zero will return 1 because zero factorial is 1.
Okay so our recursion chain will stop here.
We do not need to go any further.
Okay so factorial zero will give this output will give its output to factorial 1.
Okay so we are returning 1 here.
Okay.
Similarly factorial 1 will do its work and it will return the factorial of 1 and so on.
Okay so in recursion we call the same function with the smaller input size.
Okay we are calling the same function with the smaller input size.
Now with the help of the output of the smaller problem we have to calculate our output.
Okay so with the help of I am repeating myself with the help of the output of a smaller problem we have
to calculate our output.
Let's say the output of three factorial.
So this is bigger problem and this is a smaller problem.
Let's say the output of factorial 3 is x.
Okay so what factory 4 will do.
It will multiply forward with X and then it will return the output to the mean.
Okay.
So with the help of the output of the smaller problem the function we will calculate our bigger problem
and then we will return our output to the mean.
Okay so to stop the recursion chain what we have to do we have to stop our recursion chain here because
0 factorial is a very trivial problem.
We already know Don.
So why to why to make call to minus one.
Okay now let's see so we have to call we have to stop
we have to stop that equation.
Chin now to stop the occasion.
I know.
If the value of any zero.
I already know the answer.
Zero factoid Lisbon one so I will attend one here.
Okay now this we have an occasion Jane will stop.
Okay let's run this file
so let's then put this forward okay.
So what is happening it is the value of this forward and then it becomes T.
Then it becomes true then it becomes one then it becomes zero.
Now let's see here.
We are not making gold two minus one.
Okay.
Our our function our equation Jean stops at zero.
Okay.
We didn't call on minus.
We stopped at zero and this is our answer 24.
Okay so 24 is the fourth factorial.
Okay so our output is right now let us drive another code how it is working.
Okay
so this is I mean okay.
So main is calling factorial for
okay.
So the value of and is four here and what is happening here is when mean cause effect forward function.
So the main function it is waiting for the actual forward function to return it sunset.
Okay.
So this main function we are waiting at line number 16.
Okay.
I am also writing the line number at which the function is waiting.
So this main function is waiting at line numbers 16 for the factorial function to do its work to complete
its work.
Okay.
So I will enter defect world function and then we are again making the call the value of n is not zero.
Okay.
The value of in this word.
So I am making the call to fact function.
So this is calling factorial to function.
The value of in history and this is waiting at line number eight.
OK effectively forward.
Function is waiting at line number eight.
Now again three is not close to zero.
So it is it will call factorial to function.
And this is also waiting at line embodied the value of and is to.
Now again 2 is not zero.
So it will call factorial 1 function.
So the value of n is 1 and it is waiting at line number it again it will be a red line number it because
1 is not 0.
So it will call effectively zero function.
Okay.
The value of n is 0 now.
Okay.
So the value of end is zero okay.
So this condition is true.
What I am doing here is I am returning when so what.
What will happen.
I am returning when.
So this factoid zero function it will return when it is returning when and we added.
Line number 8.
So headline number 8.
Small I said.
So the small line said it is one here okay.
Now and multiply small answer.
So what is the value of in one small line is 1.
So it will return when multiply 1 which is 2.
So it is returning to and the two waste will be stored in this small answer.
So small answer becomes 2 now factorial 2 will do its work.
Okay so.
So it will be 1 I told you and no factor to will do its work.
So to multiply small answer.
So small answer will now becomes to here.
Okay now three multiplied two and multiply small answer so three multiply two.
So it will return six to the factory for function.
So the small answer becomes six eight.
Now and multiply a small answer and it's for small answer is six.
So it will done six into four 24 to the mean.
Okay.
So the headline number 16 I'm returning to a default.
So answer contains 24 and I am printing 24 here okay.
So you know what happened here is when I reach suppose when I am reaching this function when I use this
function all these functions they are out of memory.
Okay.
They do not exist anymore.
Okay.
So their wait is over.
They are out of memory so what is happening it is as soon as this function is returning when as soon
as this function is attending when.
Now this function does not exist as soon as this function returns its answer.
Now this function does not exist.
Okay.
So as soon as vector to function gets down from the factory one function it's where it is or what.
Similarly as soon as the actual tree function gets that would put a de facto right to function.
It's where it is or what.
And so on.
Okay so we call it go back.
Okay.
This is called strike.
I think we have already discussed it in functions.
So what is a call stick.
So Ghost tech is like a glass so at the bottom we have the main function.
Okay so we have the main function main function is calling the factorial for function factorial for
function is calling factorial 3 function factoid 3 function calls factorial 2 function factorial 2 function
calls for 3 1 function and effectively 1 function is calling factoid 0 function.
Okay.
And effect 0 0 function is not calling anything.
Okay so what is that call a stick.
So what really happened so factoid 0 will do its work.
It will complete its work and it will return the answer to defect relevant function and then it will
goes out of the memory.
Okay well it goes out it will go out.
Factory one function they compute it works and it will return the answer to the factory to function
then factory won't function they go out okay.
And this way everything will go out okay.
Everything will go out of this tank okay.
So we call it call stack we have already discussed it in functions.
Okay.
So the order is reverse okay.
Factories 0 function.
So the factorial 0 function it comes at last.
But it goes out first.
Okay.
This function mean so mean comes head first but it will go last.
Okay.
It will wait for the other function to compute their work.
We do not need to go in so much depth.
We will discuss something in the next session which is going to make things very easy for us.
Okay.
But this is how that equation works internally okay.
This is how that equation works internally.
Now I hope you got the idea how the recursion is working.
Okay if you want if you want you can optimize this code.
Also how we can optimize.
So first of all this is not required now.
There is one small but no discord.
Whatever the value of an is minus one.
Okay what if the value of end is minus 1 then it will never stop again it will become infinite loop
let me show you.
So let's say the value of n is minus 1.
A negative value then not a good.
Then again it will run into infinite loop.
Okay.
Okay so let's come and it our first.
Now let's see the value of this minus.
I will give the value of n negative so minus 1.
So again we are getting infinite loop y infinite loop because this is the beginning condition.
Okay now the value of N will never be 0.
It will keep on reducing.
So that's why.
So that's why this will run into infinite loop.
Now to fix this problem what we can do here is we can we can write a condition like if the value of
land is negative I will return minus 1 Okay factor for negative numbers are not defined.
Okay so in this case if I will give the input a negative number let's say minus 5.
So what will happen.
So we are getting minus 1 okay because vector for negative numbers is not defined McCain coming down
this code.
Okay.
So the value of an is minus 5 and the answer is minus 1 because vector for negative number is not defined.
Okay.
Now this is the correct code.
Okay.
We are using recursion here.
Okay.
Thank you.