Recursion overhead -- how serious is it?
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
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.