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