Avoiding argument checking in recursive calls

Aaron Brady castironpi at gmail.com
Wed Feb 11 09:41:39 CET 2009


On Feb 10, 7:58 pm, Steven D'Aprano
<ste... at REMOVE.THIS.cybersource.com.au> wrote:
> 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?
>
> --
> Steven

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



More information about the Python-list mailing list