[Python-Dev] Tail recursion
Andrew Koenig
ark-mlist at att.net
Thu Nov 27 12:40:11 EST 2003
> 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?
More information about the Python-Dev
mailing list