By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
464,571 Members | 965 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 464,571 IT Pros & Developers. It's quick & easy.

Re: Why is recursion so slow?

P: n/a
On Sun, 29 Jun 2008 10:03:46 -0400, Dan Upton <up***@virginia.eduwrote:
>On Sun, Jun 29, 2008 at 1:27 AM, Terry Reedy <tj*****@udel.eduwrote:
>>

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
Jun 29 '08 #1
Share this question for a faster answer!
Share on Google+

This discussion thread is closed

Replies have been disabled for this discussion.