# [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).

```