[Python-Dev] Tail recursion

[Andrew Koenig]

> Easy to understand, but it's not tail-recursive, so isn't an example of
> what
> was suggested for Brett to investigate.  I think a tail-recursive version
> is
> more obscure than your iterative one:
> 
>     def numdigits(n):
>         def inner(n, lensofar):
>             if n < 10:
>                 return lensofar
>             else:
>                 return inner(n//10, lensofar+1)
>         return inner(n, 1)

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

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 and would
prefer that the compiler do it for me.

> A different approach makes iteration much more natural:  the number of
> digits in n (>= 0) is the least i >= 1 such that 10**i > n.  Then
> iterative
> code is an obvious search loop:
> 
>     i = 1
>     while 10**i <= n:
>         i += 1
>     return i
> 
> Play strength-reduction tricks to get exponentiation out of the loop, and
> it's (just) a teensy bit less obvous.

This code relies on 10**i being exact.  Is that guaranteed?