Stack Frames. Factorial recursive vs iterative

[Yezman]

Text - My question below
-------------------------------------------------------
Let's consider the resource costs of the recursive version of
factorial:

int factorial(int n)
{
if (n == 0) {
return 1;
} else {
return n * factorial(n-1);
}
}

Compare this to a version with a loop:

int fact_iter(int x)
{
int result = 1;
while (x) {
result *= x;
x--;
}
return result;
}

Questions for the class, small groups ~5 minutes:

* How many multiplications does each version perform?
* How much space does each one require?

Both require x multiplications. So, the two run in "approximately"
the same time (though the recursive version will be a bit slower,
because a function call is a bit more expensive than a loop branch.)

We say that the performance scales linearly with the complexity of the
problem, because if we were to draw a graph with running time (or the
number of multiplications) on the y-axis as a factor of the number x,
where we are computing x!, then the graph would be a straight line.

The iterative version requires only one activation record: enough room
to hold result and X. Thus, it is constant with respect to X.

The recursive version requires X stack frames, though each one is
smaller---it only holds x. However, for large x, the recursive version
requires LOTS more space! The space requirements for the recursive
version scale linearly.

So, the recursive version is much less efficient in terms of space!
We will think about how to solve that next time.
--------------------------------------------------------------

In regards to the space. The iterative version only requires one record... that makes sense to me seeing as you are just incrementing x the whole time.

But why does the recursive version require so much more space? Couldn't it also just alter x? Or does it have something to do with calling the function again.

Like. Say you have
int main()
1.{
2. int x;
3. x = factorial(3);
4.}
So the stack originally has 1. X:
Then it goes to X: N:3

From I thought it would just keep updating X and moving N down. But that's wrong.

Does it have something to do with the fact that the function calls itself? So it goes like... X: N:3, X: N:3 N:2? I am having trouble visualizing/understanding why the recursive version uses so much more space.

Thanks!

[coder777]

any parameter that is passed to a function is placed on the stack (the stack 'grows') and is removed when the function finishes. So recursive functions places one variable after another on the stack.

As long as the stack is large enough it's no problem, but the stack action is not for free though (time wise). The space is rather irrelvant as long as it doesn't exceed the capacy of the stack

[Eyad]

Put it within a source code format, to make it clear, don't expect anyone to read your mess