Software bugs aren't inevitable
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
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