Recursion overhead -- how serious is it?

Question

Possible Duplicate:
Is recursion ever faster than looping?

I was first trained to program seriously in C, about 15 years ago. My employer wanted highly optimized code for computationally difficult tasks. I remember being advised more than once to rewrite recursions as loops, even at the expensive of readability, in order to avoid "recursion overhead." As I understood it then, recursion overhead was the extra effort required to push data onto a stack and later pop it off.

Now I code in C, Python, Perl, and sometimes Java, and I wonder sometimes about recursions. Is there still something to be gained by rewriting them? What if they're tail recursions? Have modern compilers made all these issues moot? Are such concerns irrelevant for interpreted languages?

Answer 1

I don't think any of the languages you mentioned require that the platform/compiler implements tail call elimination. You can find languages that do require this optimization - most functional languages have this requirement.

However another thing you need to consider is that computers have become orders of magnitudes faster than they were 15 years ago, so it's much rarer now then before that you need to worry about micro-optimizations. A program that 15 years ago might have required careful hand optimization in assembler to get decent performance might run blazingly fast on a modern computer, even if written in a higher level language like Java. That's not to say that performance is never a problem any more - but you should concentrate on choosing the correct algorithm and on writing readable code. Only make micro-optimizations after you have measured the performance and you can see that the code in question is the bottleneck.

One thing you do need to worry about though is overflowing the stack. If there's any risk of that happening it might be worth rewriting a recursive function in an iterative way instead.

Answer 2

It is serious. Most of the languages I code in have a real cost to function calls (the compilers for them can generally do tail recursion as well so sometimes it's not an issue).

That cost, and the fact that the stack is not an unlimited resource, usually makes me tend to use recursion only for cases where I know there's a limit on the depth it can go to.

For example, I know a balanced binary tree search will only go fifty levels deep for one quadrillion entries. I wouldn't, however, use:

def sum1through (n):
    if n == 0 return 0
    return n + sum1through (n-1)

since doing that for n of twenty million would not be healthy for a stack.

Answer 3

The issue still exists. Recursion takes a lot of stack space, as each time a method calls itself, a pointer to it and its local variables are generated again. The number of function calls made during recursion makes an O(n) memory usage; compared to O(1) of a non-recursive function like loops.

Answer 4

Recursion can lead to significant overhead if the kernel of the recursive function is less computationally expensive than the function entry/exit code and the cost of the call itself. The best way to find out is simply to profile two versions of the code - one recursive, and one not.

That said, if your idea of avoiding recursion is to make a stack-like structure yourself, watch out - it may not necessarily be any faster than the more straightforward recursive approach. Again, profiling is your friend.

Finally, remember that programmer time is more expensive than CPU time. Before you micro-optimize your code, it really is a good idea to measure to see if it really will be an issue.

Answer 5

People say lots of silly things about performance.

1. If you need recursion, like to do depth-first tree walk, then you need it, so use it.

2. Before worrying about the performance of anything, find out if you have a problem and where it is.
   Performance problems are like con men and tricksters - they specialize in being where you least expect, so if you're worried about something specific like recursion, you are almost guaranteed to be worrying about the wrong thing.

In my opinion, the best way to find performance problems is by stack sampling on wall-clock time, and examining the samples to see what the program is doing, not just by getting measurements and wondering what they mean.

That said, if you do find 10% or more of time going into a recursive call, and nothing much else happens inside the recursive routine, and you can loop it, then looping it will probably help.