Recursion vs. Iteration

[Slougi]

Hello again everyone,

Here I come again with my stoopid questions This time it is about recursion and iteration in code, as the name implies.

Having done some simple testing for various cases of sorting and manipulating variables otherwise, it seems that recursion is often faster than iteration with floats, while iteration has an edge with integers. At least that is what I got with gcc 3.3. Why is that?

On another note, I have heard that recursion generally is a bad choice if iteration would work as well, at least tail recursion. Is this just because of programming style and code readibility, or are there some other reasons for this?

Thanks for listening to my rambling and stay tuned for more stooopid question coming to a browser near you soon

 

[Teamz]

It depends what kind of task you're doing but a problem you might encouter is overloading the stack, because all your function calls and local variables are stored on the stack

 

[Slougi]

It depends what kind of task you're doing but a problem you might encouter is overloading the stack, because all your function calls and local variables are stored on the stack

I am aware of that, as I had one of my test apps inexplicably crash Took me a little before I realized the cause.

It is not really relevant to the questions I asked though

 

[milen]

Recursion is slower in most cases and is generaly not a good choice. Every recursion algorithm has iteration analog. One common method is converting recursion to iteration. There some simple rules for that. If your choice is to use recursion be sure to make your own stack implementation with functions to manipulate it.

 

[Eagle]

I agree with milen except to say recursion is also easier on the programmer. I can do simple recursive double linked list operations in 3 or 4 lines where as iteration takes a lot more thought. Milen said recursion is slower. I dont think it is, but what I think he meant to say is that the stack eats more memory than iteration does (which can make it slower I suppose). But I dont find it becomes any slower recursively, you just have to be carfull you dont overflow the stack. The small sacrifice is well worth it in most cases. Unless you are being extremely picky about speed/memory usage. If your program is a taskbar icon that runs all the time, save your users and use iteration. But if it just runs once, go with recursion as its easier to think of.

 

[Doomulation]

Recursion is generally slower due to that it's a function call. Every time a function is called, the system looks for it as to say. Plus, as said, it eats much more memory and easyily overflows the stack. I find recursion only necessary at never-ending things in code.

But eh well...in most cases, interation works, in which you should try to avoid recursion

 

[tooie]

recursion might be slower cpu wise since you got an extra function entry/exit code .. but this extra overhead is probaly meanless on computers ..

recursion to program and to maintain is a lot easier so it is quicker in programmers time. Unless the function is used dramaticly and that small increase will then cause in an impact (maybe 0.00001% of the time) then the programers time is more valuable then the computers .. so I would prefer to go for recursion

 

[Slougi]

Hmm, lots of replies both ways. I guess this is one of those things were people can never quite agree

Thanks for the replies everyone.