In this case, is recursive faster than iterate?

[MingTian]

It is well known that recursive is slower than iterate in most cases.
However, I am wondering is that true in codes like the following.
I think they are almost the same, because they both call f() 5 times. That's, they both build stack for f() 5 times. Am I right?

///////////////////////////////
// iterate

f()
{
//do some work
}

for (int i = 0; i < 5; ++i)
{
f();
}

////////////////////
// recursive
static int i = 5;
...
f(int i)
{

if (i > 0)
{
// do same work
f (--i);
}
}

[cma]

Well, there is one difference, the recursive one would take more stack-space, while the iterative solution would take less. The recursive function, by the time it reaches its terminating condition, there would be 5 different copies of i on the stack, while with the loop, only one copy of i is on the stack at any one time. In terms of speed, both should be roughly the same.

[RoboTact]

But if there are many cycles (about some Kbs or Mbs of stack size) the iterative one would be faster because of better utilising of cache.

[MingTian]

Thank you all.

And, would RoboTact please give some more information about " better utilising of cache"

[highpriest]

If I remember right (some years ago since I last wrote a assembler code), then the difference between iter. and rec. should be the below description.

The iter. alg. is faster, if the value of i is hold in accumulator of CPU. The rec. alg. realizes the stack by ESP register which points to the memory relativ to the alg. maschine code. In this memory portion is a pointer to the memory adress, where the value of i is hold. Therefore the alg. reads at first the pointer to adress and then the value of i both from much slover memory the the CPU accumulator.

The most (maybe all) compilers will realise the i for the iter. alg. in accumulator according to standard optimize parameter.

Dont hesitate to currect me, if I'am not right.

[_uj]

It is well known that recursive is slower than iterate in most cases.

I'm not so sure about that. You can always turn a recursive algoritm into an iterative but if it's a problem with a natural recursive structure this will require the use of an explicit stack. In my view the highly optimized runtime call stack should always be faster than a stack you implement yourself in the language. So in my view recursion is always faster than iteration WHEN it's used to solve problems with an inherent recursive structure AND it's only in these cases you should use recursion at all.