Avoiding argument checking in recursive calls

Terry Reedy tjreedy at udel.edu
Wed Feb 11 10:31:10 CET 2009


> Steven D'Aprano <steven at REMOVE.THIS.cybersource.com.au> writes:
>> def fact(n):
>>     if n < 0: raise ValueError
>>     if n = 0: return 1
>>     return fact(n-1)*n 
>>
>> At the risk of premature optimization, I wonder if there is an idiom for 
>> avoiding the unnecessary test for n <= 0 in the subsequent recursive 
>> calls?

Reverse the test order

def fact(n):
     if n > 0: return fact(n-1)*n
     if n == 0: return 1
     raise ValueError

You must test recursive versus terminal case every call in any case.
Nearly always, the first test passes and second is not done.
You only test n==0 once, either to terminate or raise exception.
This works for any integral value and catches non-integral values. 
(There is some delay for that, but only bad calls are penalized.)

Terry Jan Reedy




More information about the Python-list mailing list