Recursion overhead -- how serious is it? [duplicate]

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

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 2

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 3

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.