Recursion vs. Iteration

[simpleid]

Is there a worth-while benefit in performance to using recursion over iteration? I'm just really curious about the difference in the methods during a 'heavy' process.

I suppose the exact nature of the problem matters in determining Iteration vs. Recursion... so maybe someone can also elaborate on the border line decisions between the two. An obvious implementation would be in linked lists and binary tree's, but where's the 'line of preference' between these implementations and any other normal case where you'd typically think to use a loop for everyone?

Obviously in Binary Tree's recursion produces cleaner code as well, and if that's the only real noticeable benefit then to me it's still worth-while. But what about in graphing functions in OpenGL? Whether that's a preferred method or not isn't in question, just from the performance aspect.

Are there any ways in using recursion that typically a programmer may not think of? Anyone come up with some creative code and can offer some insight on testing with the methods?

Thanks.

[CornedBee]

Typically, iteration is faster than recursion. You use recursion where it considerably simplifies the code.

Clean code is more important than fast code. You can optimize the code when profiling shows that it's necessary.

[robwhit]

using recursion to traverse large data sets can crash your program. Each time a function call is made, it puts information onto the stack. Each time a function exits, a little information is taken off of the stack. Since stacks are not made large, typically, if you don't take calculated measures for code that makes a huge number of embedded function calls, you may end up with a stack overflow on your hands.

[Prelude]

>Is there a worth-while benefit in performance to using recursion over iteration?
The general rule of thumb is that recursion gives you a performance hit, not a boost. That's not always the case, but it keeps the recursion happy freaks at bay.

>but where's the 'line of preference' between these implementations and any other normal
>case where you'd typically think to use a loop for everyone?
If the iterative code is complicated, the recursive code is not complicated, and the recursive solution breaks down the problem by at least half with each call, you've got a good candidate for recursion. Anything less and I would question why you're not using loops.

>Obviously in Binary Tree's recursion produces cleaner code as well
That's where I'd disagree. I think that in many realistic tree implementations, recursion actually complicates the code and scrambles the logic. Compare the usual AVL insertion using recursion to a good implementation that doesn't. The passing and returning of information between recursive calls turns the code into a horrible mess.

[dwks]

I prefer not to use recursion, unless the iterative solution to a problem is very difficult to program.

On the other hand, the (typical) performance hit induced by using recursion is usually irrelevant if the function will only recurse a few times.

You should also be aware that some compilers can optimise recursive functions into iterative code. Don't count on this, but it can happen.

[AverageSoftware]

If you know ahead of time how many iterations/recursions you need, there are some nifty tricks using templates that can give you the functional convenience of recursion with the performance benefits of iteration. The better template metaprograms even produce unrolled loops from what appears to be a function call.