Avoiding argument checking in recursive calls

Terry Reedy tjreedy at udel.edu
Thu Feb 12 18:24:43 CET 2009


Steven D'Aprano wrote:
> On Wed, 11 Feb 2009 04:31:10 -0500, Terry Reedy wrote:
> 
>>> 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.)
> 
> Nice try, but in fact no.

I meant non-integral numbers.  Others inputs are outside the usual spec 
for fact().  You asked about "an idiom for avoiding the unnecessary test 
for n <= 0 in the subsequent recursive calls?" and I gave you that.  You 
should have thanked me.

>>>> fact(None)  # works okay
> Traceback (most recent call last):
>   File "<stdin>", line 1, in <module>
>   File "<stdin>", line 4, in fact
> ValueError
>>>> fact({})
> Traceback (most recent call last):
>   File "<stdin>", line 1, in <module>
>   File "<stdin>", line 2, in fact
> TypeError: unsupported operand type(s) for -: 'dict' and 'int'
> 
> You're relying on arbitrary ordering of types in Python 2.x,

No I'm not.  I don't even know what you mean by that claim.

> and of course in Python 3 that fails altogether.

In 3.0, which is what I use, the comparison 'n>0' raises an exception 
for non-numbers, as it should.  To me, that is success.  What else would 
you want?

Terry Jan Reedy




More information about the Python-list mailing list