Home Original page

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

Bengt Richter bokr at oz.net
Mon Nov 10 01:06:30 EST 2003 
On Sun, 09 Nov 2003 20:56:39 -0800, David Eppstein <eppstein at ics.uci.edu> wrote:

>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).
>
I played with fibonacci and was quite proud of myself for having
probably rediscovered a fast recursion algorithm for it
(about this time 1996 it seems, sheesh time flies) :

in scheme

http://groups.google.com/groups?selm=52s6qm%24rdp%40kanga.accessone.com&output=gplain

and later I translated it to python

http://groups.google.com/groups?selm=3b4a468d.1494788532%40wa.news.verio.net&output=gplain

Perhaps you know of a similar predecessor?

BTW, do you mean dynamic programming above as in Bellman? Recursion can be used in
implementing that, but for fibonacci how would it apply?

Regards,
Bengt Richter
More information about the Python-list mailing list