Thomas A. Russ wrote: > "Pascal J. Bourguignon" <p...@informatimago.com> writes: > >> Roland Hutchinson <my.spamt...@verizon.net> writes: > >>> Tail recursion can always be turned into an iteration when it is >>> executed. >> All recursions can be turned into iterations, before execution. > > True, but only by simulating the call stack in the iterative code. To > my mind that isn't really an iterative algorithm anymore if it ends up > simulating the call stack.
When does a data structure stop being a simulation of a stack? I've often had to turn recursive algorithms into iterative ones, where the solution turned out to be "simulating the call stack" only in a very broad sense; a big stretch of the imagination is needed to see the equivalent of push or pop operations. > Tree walks are the canonical example of what can't be done in an > iterative fashion without the addition of an explicitly managed stack Let me throw in an example where the desired tree walk is neither depth-first or breadth-first. It's to do with the way I display my family tree on my web site; an example may be found at http://www.pmoylan.org/cgi-bin/wft.cmd?D=moylan;P=I004 Most people familiar with algorithm design will, I believe, end up deciding that the appropriate data structure in this case is a queue rather than a stack. ObAUE: In common parlance, the English word "recursion" means pretty much the same as what computing people call "iteration". This might be the first time I have ever found a point of agreement with Xah Lee. -- Peter Moylan, Newcastle, NSW, Australia. http://www.pmoylan.org For an e-mail address, see my web page. -- http://mail.python.org/mailman/listinfo/python-list
