Avoiding argument checking in recursive calls
Terry Reedy
tjreedy at udel.edu
Wed Feb 11 16:22:25 EST 2009
andrew cooke wrote:
> Terry Reedy wrote:
>> 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?
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
More information about the Python-list
mailing list