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