Software bugs aren't inevitable
Terry Reedy
tjreedy at udel.edu
Wed Sep 14 17:28:02 CEST 2005
"Steven D'Aprano" <steve at REMOVETHIScyber.com.au> wrote in message
news:pan.2005.09.14.12.05.00.913356 at REMOVETHIScyber.com.au...
> Which works wonderfully as an academic exercise, but doesn't tend to work
> so terribly well in the real world where the performance and
> resource-requirement differences between iteration and recursion can be
> significant.
I think your comparison is incomplete.
Recursion and iteration are two syntaxes for the same operation: repetition
with variation. Indeed, iteration can be viewed as within-frame tail
recursion. Recursion usually takes more space for a stack of call
frames -- unless the particular system optimizes the stack away for
particular functions (by recursing within a frame!). For a given
algorithm -- defined by what actually gets computed -- the time difference
is a small constant. For Python, recursion is probably slower relative to
iteration than for other languages because of the flexibility and slowness
of function calls.
> For instance, try these two simple functions for the nth number
> in the Fibonacci sequence:
Abstractly, these are two algorithms for the same function. One runs in
exponential time because it wastefully calculates and tosses away an
exponential number of subvalues. The other runs in linear time because it
calculates each subvalue once. When one only wants Fib(n), and not the
sequence leading up to it, even this is wasteful, for large enough n, since
there is a third algorithm that caluculates Fib(n) directly by a simple
formula (something like the interger part of the golden ratio to the nth
power).
Now: I could (and probably someday will) write an iterative version of the
exponential algorithm (using an explicit stack) that calculates each
subvalue exactly as many times as the recursive version of that same
algorithm. And I could compare it to a recursive version of the more
efficient linear algorithm (such as posted by Jerzy Karczmarczuk). And I
could claim that this shows hows iteration can waste time compared to
recursion.
But that, I admit, would be an invalid conclusion. And that, I claim, is
also invalid when 'iteration' and 'recursion' are reversed, no matter how
often repeated in texts and articles. The difference is between the
algorithms, not the differing syntactic expressions thereof.
Terry J. Reedy
More information about the Python-list
mailing list