[Python-Dev] Tail recursion
Tim Peters
tim.one at comcast.net
Thu Nov 27 12:10:56 EST 2003
[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.
More information about the Python-Dev
mailing list