Re: Why is recursion so slow?

Dan Upton a écrit :
On Sun, Jun 29, 2008 at 1:27 AM, Terry Reedy <tjreedy@xxxxxxxx> 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.)

By decision of the BDFL, based on the argument that it makes debugging harder, CPython doesn't optimize tail-recursive calls.
.

Relevant Pages

  • Re: Why is recursion so slow?
    ... etc but wow how can it be THAT much slower for computing fibonacci- ... The comparison below has nothing to do with recursion versus iteration. ... O, algorithm with a linear, O, algorithm. ...
    (comp.lang.python)
  • Re: Why dont give Miller-Rabin a chance?
    ... Steen Schmidt wrote: ... the slower the algorithm. ... I think that computer simulation oif the limits is in order ...
    (comp.sys.hp48)
  • Re: python simply not scaleable enough for google?
    ... There have been attempts to remove the GIL, and they lead to CPython becoming *slower*, not faster, for the still common case of single-core processors. ... It so happens that I think CPython could have been significantly faster, but doing that would amount to creating a new implementation, say, C++Python, and what for, really?, since CPU-intensive things should be offloaded to other language code anyway. ... Different tasks run at different speeds, and there is no universal benchmark. ...
    (comp.lang.python)
  • Re: python simply not scaleable enough for google?
    ... There have been attempts to remove the GIL, and they lead to CPython ... becoming *slower*, not faster, for the still common case of single-core ... run at different speeds, and there is no universal benchmark. ...
    (comp.lang.python)
  • Re: PRNG III
    ... slower then my algorithm. ... Cannot be performed at all in 4 keypresses on a calculator ... Quite why you consider something that is quick to be 'much slower' ...
    (sci.crypt)