Why is recursion so slow?
bruno.42.desthuilliers at websiteburo.invalid
Mon Jun 30 13:10:54 CEST 2008
Dan Upton a écrit :
> 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-
>> 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.)
By decision of the BDFL, based on the argument that it makes debugging
harder, CPython doesn't optimize tail-recursive calls.
More information about the Python-list