Software bugs aren't inevitable

Terry Reedy tjreedy at udel.edu
Thu Sep 15 02:13:57 CEST 2005


"Rocco Moretti" <roccomoretti at hotpop.com> wrote in message 
news:dg9jh7$on1$1 at news.doit.wisc.edu...
> The algorithm one uses sometimes depends quite heavily on which mindset
> you're using. Some algorithms require much more mental effort to
> understand when in their recursive form versus the iterative form, and
> vice versa. If you're stuck thinking in only one form, you might miss
> the better algorithm because it is not as "simple" in that form.

This is why I disagree with the extreme recursionist and iterationist camps 
that both argue that since both forms cover the same ground, one only needs 
to learn one.

> The ideal case would be a programming language that allows you to write
> the algorithm in whatever form is simplest/most comfortable, and then
> automagically transforms it to the form that works the fastest under the
> hood.

I suspect that recursion can be always be sped up by doing it within one 
frame.  Some languages/compilers do this for the particular form of linear 
recursion called tail recursion.    In general, recursion to iteration 
requires two stacks and two loops nested within a third, but there are 
several special cases which are simpler in one way or another.  I think 
making the right choice will generally require extra input from the 
programmer.  But with the extra info and some restraint in formatting, I 
think the rest could be automated.

A separate tranformation issue is how to reduce double recursion to single 
recursion, when possible, and even to no recursion, as one can with the 
Fibonacci example.  For functions which produce a set or sequence of 
structures, a related sort of transformatiom is from all-at-once production 
to one-at-a-time generation.

Terry J. Reedy






More information about the Python-list mailing list