Dan Upton wrote:
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.
Which is exactly why I continued with "In Python, an algorithm written
with iteration is faster than the same algorithm written with recursion
because of the cost of function calls. But the difference should be a
multiplicative factor that is nearly constant for different n. (I plan
to do experiments to pin this down better.) Consequently, algorithms
that can easily be written iteratively, especially using for loops,
usually are in Python programs."
People should read posts to the end before replying, in case it actually
says what one thinks it should, but just in a different order than one
expected.
If each call does only a small amount of work, as with fib(), I would
guess that time difference might be a factor of 2. As I said, I might
do some measurement sometime in order to get a better handle on when
rewriting recursion as iteration is worthwhile.
tjr
--
http://mail.python.org/mailman/listinfo/python-list
