[Python-Dev] Tail recursion

[Tim Peters]

[Brett]
>> I mostly agree with everything Guido has said.  It probably should
>> only be used when -OO is switched on.  And yes, iterative solutions
>> tend to be easier to grasp.

[Andrew Koenig]
> Not always.
>
> For example, suppose you want to find out how many (decimal) digits
> are in a (non-nega tive) integer.  Yes, you could convert it to a
> string and see how long the string is, but suppose you want to do it
> directly.  Then it is easy to solve the problem recursively by making
> use of two facts:
>
> 	1) Non-negative integers less than 10 have one digit.
>
> 	2) If x > 10, x//10 has one fewer digit than x.
>
> These two facts yield the following recursive solution:
>
> 	def numdigits(n):
> 	    assert n >= 0 and n%1 == 0
> 	    if n < 10:
> 	        return 1
> 	     return 1 + numdigits(n//10)

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)

>  An iterative version of this function might look like this:
>
> 	def numdigits(n):
> 	    assert n >= 0 and n%1 == 0:
> 	    length = 1
> 	    while n >= 10:
> 	        length += 1
> 	        n //= 10
> 	    return length
>
> Although these two functions are pretty clearly equivalent, I find the
> recursive one much easier to understand.  Moreover, I don't know how
> to write an interative version that is as easy to understand as the
> recursive version.  Think, for example, how you might go about
> proving the iterative version correct.

Exactly the same way as proving the tail-recursive version is correct
<wink>.

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.