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
--
http://mail.python.org/mailman/listinfo/python-list
