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

[David Eppstein]

Anton Vredegoor wrote:
> > find a better example of recursive functions that memoize and which
> > cannot be made iterative.
> > 
> > This would generate an important precedent for me because I have
> > believed for a long time that every recursive function can be made
> > iterative, and gain efficiency as a side effect.

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.

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.

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