Avoiding argument checking in recursive calls

[Steven D'Aprano]

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



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?

 

[Jervis Whitley]

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?

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.

 

[Gabriel Genellina]

En Tue, 10 Feb 2009 23:58:07 -0200, Steven D'Aprano

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



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?

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.

 

[afriere]

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

 

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

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

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?

Build a list of function calls, and just replace the base case with a
terminating call.
.... def rec( i ):
.... return i* funcs[ i- 1 ]( i- 1 )
.... def base( i ):
.... return 1
.... funcs= [ rec ]* n
.... funcs[ 0 ]= base
.... return rec( n )
....1

 

[Terry Reedy]

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

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,

 

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

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]

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]

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.


Traceback (most recent call last):
File "<stdin>", line 1, in <module>
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.

 

[Terry Reedy]

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.

Traceback (most recent call last):
File "<stdin>", line 1, in <module>

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]

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.


[...]

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.

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.