Software bugs aren't inevitable

[Terry Reedy]

"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