C++ homework help(solved thx)...

[dinkumthinkum]

A recursive function written like that (with the recursive call executed last) is called "tail-recursion" and is tantamount to iteration. A Sufficiently Smart Compiler (tm) will recognize that situation and transform the recursive call into a loop without any function call overhead. gcc knows how to do this in many situations, though I don't know whether VS2008 can (it is Microsoft, so I have my doubts). It's actually quite a common and simple compiler optimization, and is absolutely necessary for functional language compilers.

It is extremely naive to say that "recursion" is always less efficient. Especially if you go so far as to build your own stack in your attempt to "avoid recursion". That is a classic newbie mistake.

 

[Cogman]

A recursive function written like that (with the recursive call executed last) is called "tail-recursion" and is tantamount to iteration. A Sufficiently Smart Compiler (tm) will recognize that situation and transform the recursive call into a loop without any function call overhead. gcc knows how to do this in many situations, though I don't know whether VS2008 can (it is Microsoft, so I have my doubts). It's actually quite a common and simple compiler optimization, and is absolutely necessary for functional language compilers.

It is extremely naive to say that "recursion" is always less efficient. Especially if you go so far as to build your own stack in your attempt to "avoid recursion". That is a classic newbie mistake.

Putting compiler optimizations aside. So long as the "call" function is used, recursion will be less efficient then its equivalent iterative solution. The stack unwinding is what really kills things. Even doing a stack/queue based iterative solution has the possibility of being faster then its recursive counter part as the return address isn't placed on the stack (thus you go until the stack is empty). Though, that depends a lot on implementation of the stack and of course, compiler optimizations.

 

[dinkumthinkum]

Again, the point is that "tail-recursion" is tantamount to iteration and any decent compiler (e.g. gcc) will recognize that and not emit a "call" instruction.

 

[eLiu]

Again, the point is that "tail-recursion" is tantamount to iteration and any decent compiler (e.g. gcc) will recognize that and not emit a "call" instruction.

"pure" tail recursion in a form that a 'decent compiler' is willing to recognize is generally pretty damn simple (well, at least in C). I would not count on the compiler to unwind tail recursion for me unless I'm doing something that isn't much more complex than the dumb way of computing factorials.

I mean, if you're writing a (simple) for/while loop with recursion in a non-functional language, you're doing something wrong. (Exception: amt of computation is large & depth of recursion is small)