Why is recursion so slow?

[Terry Reedy]

Dan Upton wrote:
> On Sun, Jun 29, 2008 at 1:27 AM, Terry Reedy <tjreedy at udel.edu> wrote:
>>
>> slix wrote:
>>> Recursion is awesome for writing some functions, like searching trees
>>> etc but wow how can it be THAT much slower for computing fibonacci-
>>> numbers?
>> The comparison below has nothing to do with recursion versus iteration.  (It
>> is a common myth.) You (as have others) are comparing an exponential,
>> O(1.6**n), algorithm with a linear, O(n), algorithm.
>>
> 
> FWIW, though, it's entirely possible for a recursive algorithm with
> the same asymptotic runtime to be wall-clock slower, just because of
> all the extra work involved in setting up and tearing down stack
> frames and executing call/return instructions.

Which is exactly why I continued with "In Python, an algorithm written 
with iteration is faster than the same algorithm written with recursion 
because of the cost of function calls.  But the difference should be a 
multiplicative factor that is nearly constant for different n.  (I plan 
to do experiments to pin this down better.)  Consequently, algorithms 
that can easily be written iteratively, especially using for loops, 
usually are in Python programs."

People should read posts to the end before replying, in case it actually 
says what one thinks it should, but just in a different order than one 
expected.

If each call does only a small amount of work, as with fib(), I would 
guess that time difference might be a factor of 2.  As I said, I might 
do some measurement sometime in order to get a better handle on when 
rewriting recursion as iteration is worthwhile.

tjr