[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