Home Original page

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

David Eppstein eppstein at ics.uci.edu
Mon Nov 10 01:17:12 EST 2003 
In article <bon9t6$ndl$0 at 216.39.172.122>, bokr at oz.net (Bengt Richter) 
wrote:

> 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&o
> utput=gplain
> 
> Perhaps you know of a similar predecessor?

You're in good company, this looks pretty similar to or the same as the 
one rediscovered by Dijkstra in
http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD654.PDF
(bottom of page 1).  He called it "well-known" in 1978 but I'm not 
familiar with earlier references.

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