Avoiding argument checking in recursive calls

Paul Rubin http
Wed Feb 11 08:41:18 CET 2009


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?

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.



More information about the Python-list mailing list