recursion vs iteration (was Re: reduce()--what is it good for?)
David Eppstein
eppstein at ics.uci.edu
Mon Nov 10 05:56:39 CET 2003
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
More information about the Python-list
mailing list