Welcome back.
Previously we have discussed how we can find n factorial using recursion.
So that's the pseudocode we have over here.
It's interesting to note that we could have achieved the same thing.
That is we could have found n factorial iteratively as well.
So that would be something like this.
Let's say initially factorial is set to one.
And then we iterate from 5 to 1.
And then we just keep multiplying.
So initially fact is one.
And then I is five.
So this becomes five into one.
And then I becomes four.
So we multiply to this four and then this becomes three.
So we multiply it and we multiply two and we multiply one.
So this over here also gives us five factorial.
It's interesting to note that whatever we did using recursion could also be done using iteration.
So this is an important thing that you should know.
Things done recursively can also be done iteratively.
Another thing to note when we compare recursion and iteration, is that an advantage of iteration over
recursion is that it does not use space on the call stack.
Recursion call stack.
Okay, so we have seen the recursion call stack.
We've visualized it.
It's something like this right.
We had all the calls over here.
So when we solve the same problem iteratively we do not use recursive call stack space.
So therefore you will see that in many coding interview questions you can achieve a better space complexity
with an iterative solution as compared to a recursive solution.
So this is another interesting point when we compare recursion and iteration.
Another interesting point.
And let me make some space over here when we compare recursion and iteration, is that recursion has
both an ascending phase as well as a descending phase.
Now what do I mean with that?
Again, let's first take a look at iteration to understand this in a better manner.
When it comes to iteration, it only has the ascending phase.
So this means that we go from I equal to 5 to 1 in this case, and we iterate from 5 to 4 to 3 to 1,
2 to 1.
And that's it.
Right?
So there is no coming back.
Once we've gone from 5 to 4, there is no coming back to five again.
But when you take a look at recursion, notice over here that once we have like again let's let's take
a look at the recursion call stack.
So let's say we have f of five over here.
And we have f of four over here.
And we have f of three over here.
Let's say F of one is popped out, F of two is popped out, and then we come back to F of three.
So let's say we are again in the body over here.
Notice that we are again over here when we get the value right.
When we get the value of f of two, we are over here and we can do more things over here.
I could print something or I could do some other operations.
So recursion has not only an ascending phase, which is what iteration has, but recursion also has
a descending phase.
So this is something interesting which we can use in different questions.
So the bottom line is that everything that is done recursively could be done iteratively.
And we have seen that iterative solutions have better space complexity.
So why use recursion if this is the case.
The answer to that is that solutions written in a recursive way are many times more readable and easy
to write and comprehend, especially when it comes to complex questions.
So that is why recursion is a powerful tool, even though it has some disadvantages, such as it using
more auxiliary space.