[Python-Dev] Tail recursion

[Andrew Koenig]

> 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.

Not always.

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.