[Python-ideas] Tail recursion elimination

[spir]

On 01/19/2014 01:45 AM, Steven D'Aprano wrote:
> What makes you say that it is "non-pythonic"? You seem to be assuming
> that *by definition* anything written recursively is non-pythonic. I do
> not subscribe to that view.

It is certainly hard to judge the size of the field of "naturally" recursive 
algorithms. First it depends on applications or application domains, on thinking 
habits, on kinds of data structures... one is accustomed with. Second, there is 
much vagueness and ambiguity on the very term of recursion in programming. 
Recursion and recurrence just mean literally re-running, that is a cyclic, 
repetitive, looping, (re)iterative process.

The typical case used as example is factorial.
	fact(0) = 1      fact(n) = n * fact(n-1)

This is plain semantics. To get an *algorithm* to *compute* fact(n), one can 
interpret these semantics in 2 ways:
* forward iteration: start with base case (0) then as long as we don't reach n 
compute the next factorial
* backward iteration: start with n, then as long as we don't reach the base case 
compute the previous factorial
Both are recursive, but in programming we call the second case a recursion, 
while the former is at times called corecursion (see wikipedia); corecursion is 
just equivalent to plain loops, since moving forward, and just as easy to 
understand. [Which is for the least strange, I'd happily swap the terms.] [And 
the actual computing process of backward iteration is actually forward, indeed, 
but this does not appear in code.]

Funnily enough (since sum is rarely used as example) the trivial case of sum can 
lead to a similar reasoning.

For quite a while I played with mostly functional languages, and as a 
consequence implemented many routines as "backward recursions" (ending with the 
base case), even when back to procedural programming, especially when dealing 
with tree-like or other linked data. I remember a case of a radix trie (see 
wikipedia) which I had a hard time getting right, actually a hard time 
*thinking*. Then by pure chance I stepped on an implementation of tries in 
python, using "forward recursion", which was trivial to understand. I translated 
the logic to my C trie, very happily. This radically changed my view on 
"naturally" recursive algorithms.
That tries (and other linked data when implemented the functional way) are 
*self-similar* (see wikipedia) data structures, that thus corresponding 
algorithms too are "naturally" self-similar, does not imply that *backward* 
recursion is the natural / simple / easy way.

(Now, I do agree that
     def fact (n): return 1 if n<2 else n * fact(n-1)
is very ok: simple and easy enough... once one gets the very principle of 
backward recursion, meaning thinking recurrence so-to-say inside out.)

Denis