Recursion is a technique that allows a program to call itself one or more times until a specified condition
is met.
Once the condition is met, the calculations are then processed from the last one called to the first.
So let's start off with a pretty simple example so that we can get a really good understanding of how
recursion works.
So we will do factorial.
And you might already be familiar with this because it's pretty common.
So we have in factorial, which is the same as in times n minus one times n minus two times n minus
three and so on and so forth.
Well we can actually rewrite this as n factorial is equal to n times.
In minus one factorial.
And with that, then we can assume we have a function called factorial that takes in.
And what we can do is we can say, well, the answer to that is equal to n times the factorial of n
minus one.
So we can have this function, represent this right here.
So what does this look like when we try to calculate from the last called to the first?
Well, we can look at the call stack.
Right.
And so we'll draw it out right here.
Put a couple of.
Frozen.
And so we have.
Main.
And then we have we'll say factor five.
Factor for.
Factor of three.
Factor of two, and then we'll add another one right here just for clarity, and we will put one there.
So when we go to unwind, actually scratch, that will go this way, right?
So we start at the main function.
So this is the start.
So as we do our executions, we then call factorial of five, which then calls factorial of four, which
then calls factorial of three, two.
And then at the end we have one.
So this is the order as it.
Execute.
So remember I said recursion calculations are processed from the last one called.
So this is the.
Paul is the one.
And now we begin unwinding
our stack.
So we will have one times factorial of two.
Times factorial the three times factorial of four times factorial of five, and then our value is returned.
Is returned.
So now that we have a good understanding of how this works, let's go implement this and rust so that
we can really see it in action.