Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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?

like image 817
Josephine Avatar asked Oct 24 '10 14:10

Josephine


People also ask

Are recursive calls expensive?

Recursive calls are expensive (inefficient) as they take up a lot of memory and time. Recursive functions are hard to debug.

How inefficient is recursion?

Recursive algorithms are often inefficient for small data, due to the overhead of repeated function calls and returns. For this reason efficient implementations of recursive algorithms often start with the recursive algorithm, but then switch to a different algorithm when the input becomes small.

Can recursion cause memory leak?

From the previous example, we can see that recursive calls in co or async functions may delay the memory deallocation. This delay leads to memory pileups and memory pressure.

What overhead is involved in recursion?

A recursive algorithm incurs two kinds of overhead that are not incurred by an iterative algorithm: memory and CPU time. Both of these are direct results of the fact that recursive algorithms do a lot of method calling.


3 Answers

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.

like image 169
bdonlan Avatar answered Oct 07 '22 14:10

bdonlan


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.

like image 31
Catie Avatar answered Oct 07 '22 12:10

Catie


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.

like image 23
paxdiablo Avatar answered Oct 07 '22 13:10

paxdiablo