recursion vs iteration (was Re: reduce()--what is it good for?)

[Terry Reedy]

"David Eppstein" <eppstein at ics.uci.edu> wrote in message
news:eppstein-3EA31B.11393809112003 at news.service.uci.edu...
> Recursive memoization can be better than iteration when the
recursion
> can avoid evaluating a large fraction of the possible subproblems.
>
> An example would be the 0-1 knapsack code in
> http://www.ics.uci.edu/~eppstein/161/python/knapsack.py
>
> If there are n items and size limit L, the iterative versions (pack4
and
> pack5) take time O(nL), while the recursive version (pack3) takes
time
> O(min(2^n, nL)).  So the recursion can be better when L is really
large.

Are you claiming that one *cannot* write an iterative version (with
auxiliary stacks) of the same algorithm (which evaluates once each the
same restricted subset subproblems)  -- or merely that it would be
more difficult, and more difficult to recognize correctness (without
having mechanically translated the recursive version)?

> An example of this came up in one of my research papers some years
ago,
> http://www.ics.uci.edu/~eppstein/pubs/p-3lp.html
> which involved a randomized recursive memoization technique with
runtime
> significantly faster than that for iterating through all possible
> subproblems.

And it is surely also faster than recursing through all possible
subproblems ;-).

It seems to me that the issue of algorithm efficiency is one of
avoiding unnecessary and redundant computation and that iterative
versus recursive syntax has little to do, per se, with such avoidance.

Standard example: the fibonacci function has at least two
non-constant-time, non-memoized algorithms: one exponential (due to
gross redundancy) and the other linear.  Either can be expressed with
either recursion or iteration.  Too often, people present recursive
exponential and iterative linear algorithms and falsely claim
'iteration is better (faster) than recursion'.  I could just as well
present iterative exponential and recursive linear algorithms and make
opposite false claim.

Having said all this, I quite agree that recursive expression is
sometime far better for getting a clear, visibly correct
implementation, which is why I consider iteration-only algorithm books
to be somewhat incomplete.

Terry J. Reedy