Mag, open your eyes. The reason that a fibonacci recursively implemented is slow is because its _RECALCULATING_ values, not because its calling itself recursively. Its not a suitable problem for recursion. Stack overhead just isn''t an issue.

And I''ve got some news for you, quicksort is recursive by nature. Even if you were sorting 4 billion numbers, you''d only have to go 32 deep which is _WELL_ within the limits of the stack on any machine made after 1970.

Get over it - recursion is a practical and elegant way to solve problems. I suggest actually trying to use it before passing it off as worthless.

i didn''t say it was worhtless, its just not optimized

and yes fib is bad example, do a factorial
time it.

Saying recursion is "not optimized" is like saying "my television blue flowers". Its _meaningless_, and makes no sense. It is all in what you're using it to solve for. Just like any other technique there's a right way and a wrong way. Using it correctly is every bit as fast as iteration for the right problems.

There are _tons_ of practical, valid uses for recursion. If you can't see that, you have no idea what you're talking about. Take a theoretical CS class or two, and maybe some combinatoric math. You're just totally wrong here.

Edited by - daveb on November 12, 2000 2:02:24 AM

Some of you are saying it is best to attempt to implement recursive algorithms iteratively, in order to save the overhead of lots of function calls. In cases where your recursive function stays fairly shallow (like 8 levels max depth), you can let the compiler inline the recursive function to that depth... won't this "unrolled" recursive function be just as fast as any hand-coded iterative version?

Magmai Kai Holmlor, factorial? That's tail recursion, which most optimizing compilers convert to iteration anyway.

Edited by - Eric on November 12, 2000 4:24:47 AM

quote: Original post by Magmai Kai Holmlor
and yes fib is bad example, do a factorial
time it.

Well, as an avid user of recursion I was a bit curious myself, so why not? Playing by your rules, I went ahead and tested the two versions of the factorial function for depths from 1 to 16 (the maximum fac that will store in a uint, so as to make life easy).
Here is the source:

    #include <stdio.h>#include <time.h>static unsigned int recursiveFac(unsigned int val){	if(val<=1) return 1;	return val*recursiveFac(val-1);}static unsigned int iterativeFac(unsigned int val){	unsigned int i,res;	for(res=1,i=1;i<=val;res*=i,i++); 	return res;}void main(){	unsigned int i,j,time;	for(i=1;i<=16;i++) {		time = clock();		for(j=0;j<10000000;j++) {			iterativeFac(i);		}		printf("Depth=%2d\tIteration: %f\t",i,(float)(clock()-time)/CLOCKS_PER_SEC);		time = clock();		for(j=0;j<10000000;j++) {			recursiveFac(i);		}		printf("Recursion: %f\n",(float)(clock()-time)/CLOCKS_PER_SEC);	}}And here are the results:[source]Depth= 1	Iteration: 0.820000	Recursion: 0.550000Depth= 2	Iteration: 1.040000	Recursion: 0.830000Depth= 3	Iteration: 1.260000	Recursion: 1.150000Depth= 4	Iteration: 1.540000	Recursion: 1.540000Depth= 5	Iteration: 2.470000	Recursion: 1.860000Depth= 6	Iteration: 2.810000	Recursion: 3.180000Depth= 7	Iteration: 3.080000	Recursion: 3.680000Depth= 8	Iteration: 3.350000	Recursion: 3.790000Depth= 9	Iteration: 3.680000	Recursion: 3.850000Depth=10	Iteration: 4.010000	Recursion: 4.560000Depth=11	Iteration: 4.330000	Recursion: 5.000000Depth=12	Iteration: 4.620000	Recursion: 5.710000Depth=13	Iteration: 4.890000	Recursion: 5.380000Depth=14	Iteration: 5.270000	Recursion: 5.660000Depth=15	Iteration: 5.550000	Recursion: 6.480000Depth=16	Iteration: 5.880000	Recursion: 7.300000  

I compiled this with MSVC 5.0 and tested on a PII 300 (for 10000000 iterations). The timer routines are clearly not perfect, since they are going on realtime and show some deviation in the results, but given that the conditions were the same for the two tests it shouldn't be much of a factor. In this test, I don't see too much difference between the two routines.

If I were to write factorial myself, I would personally go with the iterative version because it is just as clear and concise as the recursive version. But many everyday programming scenarios do not meet this criteria nearly so well, and recursion is often the best solution because it avoids the hacks that would be needed to accomplish the same thing with iteration. The ability to implement something cleanly and quickly is many times just as or more important as doing it optimally, and this is where recursion is a lifesaver.

So here is a challenge to you: a few posts down below someone asked for some assistance in implementing the "flood-fill" problem. I posted a recursive solution, which is in my opinion the cleanest way to accomplish the task. Of course there is an iterative equivalent. Let's see it, and see how its performance compares. I'm prepared to be humbled!

Edited by - byondo on November 12, 2000 6:57:22 AM

Ok,

I looked trough all the answrs, but haven''t yet decided (BTW, nether have you). That''s sad

I don''t want to know if recursion is dangerous (God, everybody knows it''s not, it''s been around for too long... ). I wanted to know if I get some measurable performance gain if I used iteration. I don''t care about the implementation, better think two hours, and then have 10-15% performance gain than think two minutes and screw the performance gain, right? After all, that 10-15% can be used in AI elgorithms and stuff, right?

Thanks for your opinions, and I await new ones,
Adrian "cearny" Cearnau

Sorry about forgetting to login before posting, and for the mistakes in the text!

Hi again,

Ok, did some research. Let's forget about qsort, or factorial, and go to something more complex, like Catalan's number...

(_ 1 ___ AA _ n ____ 1 ___ (n+1) * (n+2) * ... * 2n
( --- * A__A ____ = --- * --------------------------
( n+1 _ A _A 2n __ n+1 __ 1 * 2 * ... * (n-1) * n

...where A stands for arrangements.

As I had to calculate Catalan's number up to 2455, I had to implement big numbers:

struct bn {
unsigned short c[2048]; // the digits
unsigned short l; // number of digits (length)
};

My first approach to multiplying big numbers ( you probably have noticed that you only have to du multiplications, as the lower part of the fraction reduces ) was a recursive one...

if( c_digit
... but i quickly realized that you need only to use recursive functions when you can't _possibly_ use something else... and when you have lots of data you can process in one loop...

My second approach was smarter. I implemented a function to simply multiply each digit of the bn structure, (Homework: do that both recursive and iterative( loop ), and see witch one is faster ).

Still awaiting your opinions,
Adrian

PS: Sorry about the underlines, but I haven't found a way to make the text not move( and forgot what the tag was.. ;nbsp; prehaps? )

Edited by - cearny on November 12, 2000 5:01:57 PM

Edited by - cearny on November 12, 2000 5:04:48 PM

Edited by - cearny on November 12, 2000 5:07:19 PM

The tag is  , or you could put it in a block (without the spaces) or a [ source ][ /source ] block (again without the spaces)

-Chris Bennett of Dwarfsoft - Site:"The Philosophers'' Stone of Programming Alchemy" - IOL
The future of RPGs - Thanks to all the goblins over in our little Game Design Corner niche
          

To answer the original question
Assuming both implementations have the same algorithmic complexity, the answer is:

I think it depends...
You pay probably about 5 - 15 (extra) clock cycles for a __fastcall function call (My guess is based on you''ve got to push 3 registers, monkey with the stack pointer, jump, and then jump back, unmonkey the stack pointer, and pop the three registers.)

The longer and longer you spend inside the recursive function before "recursing" again, the less it matters.

What I think people are arguing over
I think what most people are gnashing their teeth about, is that many solutions that have O(n) complexity can be naively solved with O(2^n) complexity. However, if a O(n) solution exists for an iterative solution, one necessarily exists for a recursive one.

An important point
It is possible to implement binary tree traversal with an iterative solution without a stack ADT (!), if the structure has two modifications:
A node knows whether it is a left or right child.
A node knows has a link to it''s parent.

Since this can be shown to be true, it would seem reasonable that any recursive function may be rewritten in an iterative manner.

Summary:
The performance difference between an iterative and recursive implementation (provided they have the same algorithmic complexity) is neglible except for extremely small recursive functions.
Any iterative solution has an equivalent recursive solution of the same time complexity.
I suspect there is no such thing as an algorithm that requires a stack data structure, provided the computer has random access memory. (Didn''t Church or Turing prove this?)