Why is recursion so slow?

[Jean-Paul Calderone]

On Sun, 29 Jun 2008 10:03:46 -0400, Dan Upton <upton at virginia.edu> 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.  (If the function is
>tail-recursive you can get around this, though I don't know exactly
>how CPython is implemented and whether it optimizes that case.)

CPython doesn't do tail call elimination.  And indeed, function calls
in Python have a much higher fixed overhead than iteration.

Jean-Paul