On Sun, Jun 29, 2008 at 1:27 AM, Terry Reedy <[EMAIL PROTECTED]> 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.) -- http://mail.python.org/mailman/listinfo/python-list
