On May 18, 5:09 pm, Peter Moylan <inva...@peter.pmoylan.org.invalid> wrote: > > 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.
Maybe the common usage mirrors the facts better than the lore that half-baked programmers remain devoted to. Consider first implementations: The implementation of recursion by a typical language (eg gcc for C) maximizes generality at the cost of efficiency The implementation of a very special case -- tail recursion -- in some special languages (most notably scheme) is required to be competitive with the iterative solution. [If I remember right in Chez scheme tail recursion was more efficient than a do (iteration) because a do typically needed assignment and assignment was more expensive than parameter passing] But there is a wide spectrum of cases between the most general case of recursion and tail recursion. Some examples 1 A non-tail recursive function, with a single recursive call, when implemented naively would push the return address. This is unnecessary as only a flag needs to be pushed -- return to internal call point or return to external call point. This itself can be efficiently simulated by storing the recursion depth -- zero => jump out; > 0 => jump to internal call 2. A single function with double recursion -- quicksort is the classic -- can be implemented without recursion or stack. It just needs a set of pending begin-end pairs yet to be sorted. This may look like the stack in another guise but unlike the stack it does not need to store any function call return paraphernalia. 3. Tree recursion (though not the case of the OP) can be solved non- recursively with threading http://en.wikipedia.org/wiki/Threaded_binary_tree and Schorr Waite Deutsch http://www.cs.cornell.edu/courses/cs312/2007fa/lectures/lec21-schorr-waite.pdf In fact the only example I can think of where the full blown generality of recursion cannot be tightened is perhaps recursive descent parsing. So much for implementations. Semantically the while loop while B: statement is equivalent to the recursion: def stateiter(): if B: statement stateiter() -- http://mail.python.org/mailman/listinfo/python-list