On 10/2/2013 8:31 AM, random...@fastmail.us wrote:
On Tue, Oct 1, 2013, at 17:30, Terry Reedy wrote:
Part of the reason that Python does not do tail call optimization is
that turning tail recursion into while iteration is almost trivial, once
you know the secret of the two easy steps. Here it is.
That should be a reason it _does_ do it - saying people should rewrite
their functions with loops means declaring that Python is not really a
multi-paradigm programming language but rather rejects functional
programming styles in favor of imperative ones.
It is true that Python does not encourage the particular functional
style that is encouraged by auto optimization of tail recursion. A
different functional style would often use reduce (or fold) instead.
Some other points I left out in a post of medium length yet brief for
the topic.
1. If one starts with body recursion, as is typical, one must consider
commutativity (possibly associativity) of the 'inner' operator in any
conversion.
2. Instead of converting to tail recursion, one might convert to while
iteration directly.
3. One often 'polishes' the while form in a way that cannot be done
automatically.
4. While loops are actually rare in idiomatic Python code. In Python,
for loops are the standard way to linearly process a collection. The
final version I gave for a factorial while loop,
def fact_while(n):
if n < 0 or n != int(n):
raise ValueError('fact input {} is not a count'.format(n))
fac = 1
while n > 1:
fac *= n
n -= 1
return fac
should better be written with a for loop:
def fact_for(n):
if n < 0 or n != int(n):
raise ValueError('fact input {} is not a count'.format(n))
fac = 1:
for i in range(2, n):
fac *= n
When the input to a function is an iterable instead of n, the iterable
should be part of the for loop source expression. For loops are
integrated with Python's iterator protocol in much the same way that
recursion is integrated with list first:rest pattern matching in some
functional languages. It is true that Python encourages the use of for
loops and for clauses in comprehensions (a functional construct).
5. Conversion of apparent recursion to iteration assumes that the
function really is intended to be recursive. This assumption is the
basis for replacing the recursive call with assignment and an implied
internal goto. The programmer can determine that this semantic change is
correct; the compiler should not assume that. (Because of Python's late
name-binding semantics, recursive *intent* is better expressed in Python
with iterative syntax than function call syntax. )
--
Terry Jan Reedy
--
https://mail.python.org/mailman/listinfo/python-list
