[Python-Dev] Tail recursion

Tim Peters tim.one at comcast.net
Fri Nov 28 00:56:40 EST 2003


[Andrew Koenig]
> Ah.  I will agree with you that wholly tail-recursive programs are
> usually no easier to understand than their iterative counterparts.

Good!  That's why I've never been keen to "do something" about tail
recursion in Python -- the "one obvious way" to write a loop in Python is
with a loop <wink>.

> On the other hand, there are partially tail-recursive functions that
> I find easier to understand, such as
>
> 	def traverse(t, f):
> 	    if nonempty(t):
> 	        traverse(t.left, f)
> 	        traverse(t.right, f)
>
> Here, the second call to traverse is tail-recursive; the first isn't.
>
> Of course it could be rewritten this way
>
> 	def traverse(t, f):
> 	    while nonempty(t):
> 	        traverse(t.left, f)
> 	        t = t.right
>
> but I think that this rewrite makes the code harder to follow

I agree.  Worse still is writing it iteratively with an explicit stack.
Note that PEP 255 has both spellings for a tree-walking generator, and the
fully iterative spelling is much harder to understand.

>  would prefer that the compiler do it for me.

I don't in Python:  if I coded a call, I want Python to make a call.
WYSIWYG contributes greatly to the debuggability of large Python programs in
practice.

>>    i = 1
>>     while 10**i <= n:
>>         i += 1
>>     return i

> This code relies on 10**i being exact.

Also on + being exact, and the other code in this thread depended on //
being exact.

> Is that guaranteed?

+ - * // % ** pow and divmod on integers in Python will either deliver an
exact result or raise an exception (like MemoryError if malloc() can't find
enough space to hold an intermediate result).




More information about the Python-Dev mailing list