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

[David Eppstein]

In article <uq6dnflq6t88lTKiRVn-vw at comcast.com>,
 "Terry Reedy" <tjreedy at udel.edu> wrote:

> "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)?

Of course you can make it iterative with auxiliary stacks.
Any compiler for a compiled language would do that.
I don't think of that as removing the recursion, just hiding it.

I thought your question wasn't about semantic games, I thought it was 
about the relation between memoization and dynamic programming.  Both 
compute and store the same subproblem values, but in different orders; 
usually they are the same in complexity but not always.

> 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.

Not to mention the logarithmic (in number of arithmetic operations) 
algorithms... http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD654.PDF

> Too often, people present recursive exponential and iterative linear 
> algorithms and falsely claim 'iteration is better (faster) than 
> recursion'.

That sounds dishonest.  But Fibonacci can be a good example of both 
memoization and dynamic programming, and I would expect the iterative 
linear version to be faster (by a constant factor) than the memoized 
recursive one (also linear due to the memoization).

-- 
David Eppstein                      http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science