Avoiding argument checking in recursive calls

[Steven D'Aprano]

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.



>>> 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, and of 
course in Python 3 that fails altogether.

Thanks for everyone who responded, I now have some food for thought.



-- 
Steven