Avoiding argument checking in recursive calls

[Steven D'Aprano]

Terry Reedy wrote:

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

I thought I had made it clear that fact() was just an illustration of a
recursive function, and the test n < 0 was just a stand-in for a more
expensive test. It was toy example to illustrate a general question.
Perhaps I could have made it more obvious with a less concrete example.
Sorry for the confusion.


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

I did thank everybody who responded. That included you. I do appreciate your
suggestions, even if I ultimately choose to do something else.


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

What I understood was that you expected fact(some_arbitrary_object) to raise
a ValueError. This works if some_arbitrary_object happens to be ordered
less than 0, which only works at all because of the specific arbitrary
ordering of types in Python 2.x. In Python 3 it won't work at all.

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

I might want not to expose exceptions from the implementation, and instead
raise my own exception. For fact(), I might choose to do what you did, but
for a more complex test, arbitrary objects might fail anywhere with
potentially misleading error messages.

It's a perfectly legitimate approach to let unexpected objects fail in
unexpected ways. The advantage is that it's nice and lightweight. But it's
also a legitimate approach to have a little more control over what
exceptions are raised.



-- 
Steven