[Python-Dev] Tail recursion
Guido van Rossum
guido at python.org
Thu Nov 27 12:45:12 EST 2003
> For example, suppose you want to find out how many (decimal) digits are in a
> (non-negative) 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)
>
> 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.
Hm. The iterative version looks totally fine to me. I wonder if it
all depends on the (recursive) definition with which you started.
--Guido van Rossum (home page: http://www.python.org/~guido/)
More information about the Python-Dev
mailing list