Hi, everyone.
So in this lecture, we will start education.
OK, so recursion is one of my favorite topic.
The best part of recursion is we can easily code the most complicated problems.
OK, recursion is very important because going forward in many the structure, we use recursion only.
OK, so we have to do recursion properly, otherwise we may face a lot of problems.
OK, so what is recursion?
What is the definition of recursion?
So recursion is when a function is calling itself.
OK, the definition of recursion is when a function is calling itself so function calling itself.
OK, so this is a recursion.
OK, so now what we have seen I have a function mean man is calling a function a function E is calling
another function B and so on.
OK, but here in recursion 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 E function E is again calling function and
so on.
OK, so it is a little weird when function E is calling function itself.
OK, now let's try to think in a different manner.
OK, then 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.
OK, let's take an example.
So suppose I want to find an factorial.
OK, we want to find out what is and factorial.
So what we will do can we write like an factorial is this is N and minus one and minus two and so on
Telvin.
OK, so can I write this line.
Can I write this part in another way.
Can I write it like an factorial.
Is np multiply and minus one factorial.
OK, we can write it like this way.
Now, suppose I have a function factorial, OK, so I have a factorial function.
I will give it an and it will give me an factorial.
OK, so often it is same as can I write like this and multiply.
Factorial function and minus one.
OK, so this is the function name, fact is the function name.
OK, so this function takes Digitas argument and it will return me it will give me an factorial.
Factorial often is nothing but and multiply factorial off and minus one.
OK, so here we can see a function.
The fact function is calling the fact function but with a smaller input.
OK, so when we will use recursion, when a problem depends upon the problem of the same nature, but
with a smaller size, I am repeating myself.
We will use recursion when a problem.
Depends on a problem of the same nature, but with a smaller input size.
OK, so here we can see.
I have a problem I want to find factotum.
It depends upon the it depends upon a small problem of the same nature naturism, but with a smaller
input site.
OK, 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 reconvert the problem into smaller problem.
I will again convert it into a smaller problem.
I will again convert into a smaller problem and it will go on.
OK, so finally our problem will become very, very small.
OK, so we are reducing the size of our problem.
OK, our problem size is being reduced.
OK, we can see here our problem now our problem becomes smaller.
OK, so the question what the commission will do.
I have a big problem.
I will convert the big problem into smaller problem.
I will again convert the smaller problem into smaller problem.
Again, the smaller problem will be converted into smaller problem and so on.
OK, now let's try to see it in gold.
We will try to solve the same problem, so let us take the value of an input from the user.
OK, 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 an factorial function and it will be done with the answer and let us try to bring to
the end factorial, OK?
Now, what we have discussed, so what we return type of the function, it will be integer, then the
function is fact and it will take integer as argument, whose total we have to calculate.
OK, so.
What is the meaning of the occasion, what we will do, we will find out, we will convert the big problem
into smaller problem.
So in small answer.
I'm calling the function Vectorial and I will give and minus one.
OK, so now at number five I know the factory love and minus one.
So what is the factory?
Often it will be.
What I will do, I just have to return and multiply, Smolan said.
OK, so what I'm trying to do here is.
I want to calculate the factorial often, so headline number five, what I'm doing, I'm calculating
the factorial off and minus one.
OK, what does fact function will do?
This fact function takes an integer and it returns an integer, which is the fact of the number.
So this fact will give me and minus one factory, OK, and then minus one factorial is stored in a small
answer and finally I return and multiply and minus one factory.
OK, now let's try to add another coda and let's see what will happen.
OK.
Now it is waiting for us to give input.
Let's I want to calculate for Victoria.
OK, so Ford and.
So what will happen, what is happening here is basically we are getting segmentation fault, infinite
loop.
OK, so this is finite loop.
We are getting segmentation fault.
Now, let us try to it our code.
What is happening?
OK, let's try to try it another good.
OK.
So what is happening here is so I have this function mean.
I have this function Manitas calling the function Vectorial of an OK, so Meedan is calling.
Fact and let's say the value is for Anisfield.
OK, so Anisfield now what is happening here is this federal function is again calling the federal function.
So it is calling a federal function, but the value of industry.
So the value of these three, we can understand it this in a different way, but actually it doesn't
happen.
OK, so let's try to understand it in a different manner.
So I have mine now.
Men is calling a function vectorial.
OK.
And the value of Anisfield.
OK, now add this line, what is happening here is let's suppose we have another instance of de facto
function.
OK, we have another instance of de facto function and this is calling de facto, but the value of industry
you can see here and minus one.
OK, so this new instance is created.
You can assume that, but it doesn't happen, OK?
So now what is happening here is so what will happen?
This fact function, it will call.
Fact to.
Again, the value of an asset 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.
OK, so this and here the value of this forward and here the value of industry.
So this end and this end, they both are different.
OK, they are different.
OK, very different because we know the local variables of one function is different than the local
variables of another function.
These are two different functions.
OK, two instances.
So this and this and they both are different.
Now what will happen?
This will call fact when now the value of and becomes one.
So what is happening here is as soon as we enter this function, we are calling another function.
OK, so now this one it will call fact zero.
So the value of any zero then it will call fact minus one.
It will call effect minus two and so on.
OK, so basically it is we are doing infinite calls.
OK, we are doing infinite calls.
So this is infinite loop.
This is infinite loop.
So we are getting segmentation fault, OK.
So while 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 complete its
work.
OK, all are waiting, all have the copies off and now it is taking some memory.
OK, this is taking some memory.
This is taking some memory.
It is taking some memory.
OK, so what will happen?
We are we are doing infinite calls.
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.
OK, so when it is fact minus two, what will happen?
All these functions are waiting for the miners to function to compute its work.
OK, so everything will take memory.
They are taking small, small memories, but we are doing infinite calls.
So at some time what will happen, we will get out of memory, OK?
We will not be able to create more memory and we will get segmentation fault due to infinite calls.
OK, so why there are infinite calls because we started at an equals four, then three to one zero.
So ideally what should happen?
We should stop at zero or we should stop at one.
OK, but here we are making infinite calls.
OK, ideally we should stop at zero one, but we are making here in finite calls.
I can prove it also.
So how will I prove it.
But I will do.
As soon as I enter this function, I will print the value of an OK, I will print the value of and now
let's try to run this file.
Now, let's hear the value of Anisfield and as soon as we will bring tenter.
So you can see here, these are the values of an OK.
So these are all the values of these men number, of course, I am trying to make here.
OK, 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 the memory.
OK, so we are making many, many calls.
I don't know where it will stop.
OK, it will stop when we get out of memory and we will get segmentation fault due to lack of memory.
OK, it is making these main number of calls and it is trying to find the answer.
It is trying to find the Ford factory.
OK, so at this moment, what is happening here is we have due to lack of memory, we are getting the
segmentation fault.
OK, now let's call it up.
I'm not able to call it more, so what I've done here is.
So this is the same gold you can see here.
This is the same gold I've written this gold on radion and now let's say the inputs for and we will
try to in the file will return the gold.
OK.
So you can see the output we are getting around Tamarrod, right, and Tamira because of infinite loop.
OK, now you can see here, this is the output, four, three, two, one zero and then minus one,
minus two, minus three and so on.
OK, you can scroll to the bottom and you can see it yourself.
OK, so four, three, two, one, and then zero minus and minus two, so ideally, what should happen?
Ideally, our program should stop at some moment, OK?
Our program should stop at some moment now where it should stop.
OK, so what is happening here is Vectorial for function, this is calling Vectorial three, it is calling
Vectorial two, it is calling factorial one.
It is calling, let's say, factorial zero.
OK, now it is calling factorial minus one.
Now, according to me, there is no need of this call, why?
Because this is very trivial problem.
OK, what is zero factorial?
Zero factor Lisburn?
So I already know the answer of zero factorial.
So why to make the call to minus one.
OK, so what do factorial.
Zero Willerton one because zero factorial is one.
OK, so our recursion chain will stop here.
We do not need to go any further.
OK, so factorial zero will give this output will give its output to factorial one.
OK, so we are returning one here.
OK.
Similarly factorial one will do its work and it will return the factorial of one and so on.
OK, so in recursion we call the same function with the smaller input, says OK, we are calling the
same function with the smaller inputs right now, with the help of the output of the smaller problem,
we have to calculate our output.
OK, so with the help of I'm 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 the smaller problem, let's say the output of factorial three is X.
OK, so what factorial four will do?
It will multiply four with X and then it will return the output to the mean.
OK, 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.
OK, so to stop the recursion chain, but we have to do we have to stop our recursion, Jane, here,
because zero factorial is a very trivial problem.
We already know the answer.
So why do y to make call to minus one.
OK, now let's see.
So we have to call, we have to stop.
We have to stop the engine now to stop the recognition.
I know if the value of any zero I already know the answer is zero factorial is one.
So I will attend one here, OK?
Now this.
We have it.
It goes.
It will stop.
OK, let's end this file.
So let's say the this for.
OK, so what is happening here is the value of fairness for then it becomes then it becomes to, then
it becomes one, then it becomes zero.
Now, let's see here we are not making equal to minus one, OK, either our function of the James Dobson
zero, OK, we didn't call on minus one.
We stopped at zero.
And this is our answer, 24.
OK, so 24 is the fourth factorial.
OK, so our output is right now.
Let's try another record.
How it is working.
OK.
So this is our main.
OK, so Main is calling factorial for.
OK, so the value of and is forward here and what is happening here is when mean calls for oil for function.
So the main function, it is waiting for the oil for function to return its answer.
OK, so this main function, we are waiting at line number 16.
OK, I am also writing the line number at which the function is waiting.
So this main function is waiting at line number 16 for the factorial function to do its work to complete
its work.
OK, so I will enter the factorial function and then we are again making the call.
The value of N is not zero.
OK, the final four.
So I'm making the call to fact function.
So this is calling.
Factorial to function, the value of industry, and this is waiting at line number, if at for function
is waiting at line number eight.
Now, again, three is not close to zero.
So it is it will call factorial function.
And this is also waiting at line number eight, the value of an.
Now, again, two is not zero.
So it will call.
Factor one function, the value of N is one, and it is waiting at line, number it again, it will
be red number because one is not zero, so it will call for zero function.
OK, the value of N is zero now.
OK, so the value of any zero.
OK, so this condition is true, what I'm doing here is I am returning one.
So what what will happen?
I am returning one, so this factor zero function, it will return one.
It is returning when and we are headline number eight, so headline number eight, small answer, so
the small answer.
It is one here, OK, now and multiply SMOLAN So so what is the value of N one and it's my answer is
one.
So it will return when multiply one, which is two.
So it is returning to and the two will be stored in this.
Smolan So so small answer becomes two now factorial two will do its work.
OK, so, so it will be one.
I tell you another factor, do will do its work, so to multiply small answer, so small answer will
now be comes to here.
OK, now.
Three, multiply two and multiply Mylanta, so three, multiply two, so it will return six to the all
four function, so small answer becomes six here now and multiply Smolensky and it's for smaller answers.
Six So it will return 16 to 24 to the mean.
OK, so that line number 16.
I'm returning to India for so answer contains 24 and I am Bentinck Grandiflora.
OK, so now what happened here is when I reach the place, when I'm reaching this function, when I
use this function, all these functions, they are out of memory, OK?
They do not exist anymore.
OK, so their wait is over.
They are out of memory.
So what is happening?
It is as soon as this function is returning one, as soon as this function is that anyone now dysfunction
does not exist.
As soon as this function returns, its answer now dysfunction does not exist.
OK, so as soon as the to function gets down from the factorial function, its weight is over.
Similarly, as soon as the all three function gets the output of the factorial to function, its weight
is over and so on.
OK, so we call it Goldstrike.
OK, this is Kostic.
I think we have already discussed it in functions.
So what is a call?
Steck.
So Koscheck is like a glass.
So at the bottom we have the main function.
OK, so we have the main function.
Main function is calling the factorial for function factorial for function is calling factorial three
function factorial, three function calls, factorial to function, factorial to function calls for
one function and only one function is calling factorial zero function ok and factorial function is not
calling anything.
OK, so what is the cost.
So what will happen.
So Fatto Zero will do its work, it will complete its work and it will return the answer to de facto
one function and then it will goes out of the memory.
OK, it will goes out, it will go out effectively.
Function will complete it work and it will return.
The answer to the function then effectively won't function, will go out OK.
And this way everything will go out ok.
Everything will go out of the stack.
OK, so we call it Kostic.
We have already discussed it in functions.
OK, so the order is reversed.
OK, factorial zero function.
So the factorial zero function.
It comes at last, but it goes out first.
OK, dysfunction mean so mean comes at first, but it will go last, OK?
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.
OK, but this is how that equation works internally.
OK, this is how the equation works internally.
Now, I hope you got the idea how the equation is working.
OK, if you want.
If you want, you can optimize the score also how we can optimize so first of all, this is not required.
Now, there is one small problem with discord, what the value of and is minus one, OK, what if the
value of ND is minus one, then it will never stop again.
It will become infinite loop.
Let me show you.
So let the value of N is minus one a negative value, then our good.
Then again it will run into infinite loop.
OK.
OK, so let's come and get our first.
Now, let's see the value of an S minus, I will give the value of N negative, so minus one.
So again, we are getting infinite loop y infinite loop because this is the beginning condition.
OK, now the value of N will never be zero.
It will keep on reducing.
So that's why.
So that's why this will run into infinite loop.
Now to fix this problem.
But we can do here is we can we can write a condition like if the value of it is negative, I will return
minus one.
OK.
All for negative numbers are not defined.
OK.
So in this case, I will give the input a negative number.
Let's say minus five.
So what will happen?
So we are getting minus one, OK, because factor for negative numbers not defined.
We can comment out this.
OK, so the value of.
And is minus five and minus one because factor for negative numbers is not defined.
OK, now this is the correct word.
OK, we are using recursion here.
OK, thank you.