Avoiding argument checking in recursive calls
Steven D'Aprano
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? For the sake of the argument, let's pretend the test is expensive
and I have a good reason for wanting to avoid it on subsequent calls :)
I've done this:
def _fact(n):
if n = 0: return 1
return _fact(n-1)*n
def fact(n):
if n < 0: raise ValueError
return _fact(n)
but that's ugly. What else can I do?
--
Steven
Jervis Whitley
>
> def _fact(n):
> if n = 0: return 1
> return _fact(n-1)*n
>
> def fact(n):
> if n < 0: raise ValueError
> return _fact(n)
>
> but that's ugly. What else can I do?
>
>
def fact(n, check=False):
if not check:
if n < 0: raise ValueError
if n == 0: return 1
return fact(n - 1, check=True) * n
essentially hiding an expensive check with a cheap one. It saves you
duplicating code in a separate function like in your example.
Gabriel Genellina
<ste...@remove.this.cybersource.com.au> escribió:
I don't think it's ugly; you have an implementation (_fact) and its public
interfase (fact). In 'fact' you could check that n is actually an integer
(an implicit precondition, your algorithm doesn't finish in other case)
and whatever validation is also required. Perhaps its arguments come from
user input and you need stricter tests, or convert from other type (like
float->int).
On the other hand, '_fact' is private and you can assume their arguments
are exactly what you require.
In Pascal I would have used a nested _fact function; in Python it isn't as
efficient so I'd write it as your own example.
This is a rather used idiom - in the Python C API, by example, usually you
see a public function PyFoo_DoSomething(PyObject* obj) and a private one
_PyFoo_DoSomething(double x) (assume a function like sqrt, number ->
float). The public one takes a generic Python object, checks its type,
converts it to a C "double" value, and if all went OK, finally calls the
private implementation passing that value.
--
Gabriel Genellina
afr...@yahoo.co.uk
> Hello, an idea is optional keyword arguments.
>
> def fact(n, check=False):
> if not check:
> if n < 0: raise ValueError
> if n == 0: return 1
> return fact(n - 1, check=True) * n
>
> essentially hiding an expensive check with a cheap one. It saves you
> duplicating code in a separate function like in your example.
Given the original read:
def fact(n):
if n < 0: raise ValueError
if n = 0: return 1
return fact(n-1)*n
You've merely replaced the 'test n<0' with 'not check' at the expense
of an additional parameter that has to be passed each time (and the
additional test 'n<0' for the first iteration).
Scott David Daniels
> I sometimes write recursive functions like this simple factorial:
> 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? For the sake of the argument, let's pretend the test is expensive
> and I have a good reason for wanting to avoid it on subsequent calls :)
def fact(n):
if n < 2:
if n < 0:
raise ValueError
return 1
return fact(n - 1) * n
But really, iteration is the solution to this, and avoiding the
right answer is a mistake. I couldn't resist fixing your test
so you do one less layer of recursion.
--Scott David Daniels
Scott....@Acm.Org
Paul Rubin
> 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?
I'd write nested functions:
def fact(n):
if n < 0: raise ValueError
def f1(n):
return 1 if n==0 else n*f1(n-1)
return f1(n)
If the language implementation supports tail recursion optimization
there's an accumulation-parameter style that takes a little getting
used to but is familiar in functional programming:
def fact(n):
if n < 0: raise ValueError
def f1(k,n):
return k if n==0 else f1(k*n, n-1)
return f1(1, n)
This won't do any good in CPython but maybe PyPy or Pyrex or whatever
can make use of it. In this case the nested function is already
there, and the n<0 check naturally lifts out of it.
Paul Rubin
> I'd write nested functions:
>
> def fact(n):
> if n < 0: raise ValueError
> def f1(n):
> return 1 if n==0 else n*f1(n-1)
> return f1(n)
I forgot to add: all these versions except your original one should
add a type check if you are trying to program defensively. Otherwise
they can recurse infinitely if you give a positive non-integer arg like
fact(3.5).
Aaron Brady
Build a list of function calls, and just replace the base case with a
terminating call.
>>> def f( n ):
... def rec( i ):
... return i* funcs[ i- 1 ]( i- 1 )
... def base( i ):
... return 1
... funcs= [ rec ]* n
... funcs[ 0 ]= base
... return rec( n )
...
>>> f( 5 )
120
>>> f( 6 )
720
>>> f( 1 )
1
Jervis Whitley
> of an additional parameter that has to be passed each time (and the
> additional test 'n<0' for the first iteration).
> http://mail.python.org/mailman/listinfo/python-list
>
I think you have missed the point. The OP stated that n<0 could stand
for an expensive
operation, this replaces an expensive check every time with a cheaper
one every time.
I like the idea of the interface that was in the original post.
Cheers,
Terry Reedy
> Steven D'Aprano <ste...@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
Jervis Whitley
> You've merely replaced the 'test n<0' with 'not check' at the expense
> of an additional parameter that has to be passed each time (and the
> additional test 'n<0' for the first iteration).
andrew cooke
> 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? ie: did you think this up for
this question or is it an idiom that you find yourself using often?
andrew
Terry Reedy
> Terry Reedy wrote:
>> Reverse the test order
>>
>> 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
Steven D'Aprano
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
Terry Reedy
> On Wed, 11 Feb 2009 04:31:10 -0500, Terry Reedy wrote:
>
>>> Steven D'Aprano <ste...@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
Steven D'Aprano
> Steven D'Aprano wrote:
>> On Wed, 11 Feb 2009 04:31:10 -0500, Terry Reedy wrote:
>>
>>>> Steven D'Aprano <ste...@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