recursion vs iteration (was Re: reduce()--what is it good for?)
tjreedy at udel.edu
Mon Nov 10 04:40:12 CET 2003
"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
> can avoid evaluating a large fraction of the possible subproblems.
> An example would be the 0-1 knapsack code in
> If there are n items and size limit L, the iterative versions (pack4
> pack5) take time O(nL), while the recursive version (pack3) takes
> O(min(2^n, nL)). So the recursion can be better when L is really
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
> which involved a randomized recursive memoization technique with
> significantly faster than that for iterating through all possible
And it is surely also faster than recursing through all possible
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
More information about the Python-list