Avoiding argument checking in recursive calls

Terry Reedy tjreedy at udel.edu
Wed Feb 11 22:22:25 CET 2009


andrew cooke wrote:
> Terry Reedy wrote:
>> Reverse the test order
>>
>> def fact(n):
>>      if n > 0: return fact(n-1)*n
>>      if n == 0: return 1
>>      raise ValueError
> 
> sweet!  but is this generally possible?

I believe so, for some meaning of 'generally'.

 > ie: did you think this up for
> this question or is it an idiom that you find yourself using often?

It is an idiom I developed for an algorithm book-in-progress that will 
include  detailed comparisons of 'body' recursive (my term for 'not tail 
recursive", such as fact() above), tail recursive, and iterative 
versions of algorithms.

Here are written-for-didactic-purposes tail and iterative versions of 
fact that are computationally equivalent to the above in that they 
compute the same expression, (...((1*1)*2)*....*n), without commutative 
or associative transformation, and raise the same error (expanded).

def fact_tail(n, i=0, res=1):
     if i < n: return fact_tail(n, i+1, res*(i+1))
     if i == n: return res
     raise ValueError("Input negative or non-integral")

def fact_iter(n, i=0, res=1):
     while i < n: i,res = i+1, res*(i+1)
     if i == n: return res
     raise ValueError("Input negative or non-integral")

My original reason for writing the tail recursion in the same reversed 
order was to make the conversion to iteration as obvious as possible. 
But I them noticed that it also made possible 'test once for bad input 
without a separate function."

Terry Jan Reedy




More information about the Python-list mailing list