On 5/26/2013 8:00 AM, Ram Rachum wrote:
def factorial_recursive(n): if n == 1: return 1 return n * factorial_recursive(n - 1)
This fails for 0 (0! == 1 also), but this is easily fixed. If also fails for negative and non-integral values, but ignore that for the moment. def factorial_tail(n, result=1): if n > 1: return factorial_tail(n-1, result * n) else: return result def factorial_while(n, result=1) # written to maximize sameness with tail version while n > 1: n = n=1 result = result * n) else: return result If one can rewrite the 'body' recursion (my term) as tail recursion, the translation to while loop is trivial, and for linear recursion on counts, the for loop version is simple and ofter even clearer as it explicitly identifies all the values used in the coomputation.
def factorial_loop(n): result = 1 for i in range(1, n + 1): result *= i return result
Now consider a production ready function that will always terminate: def factorial(n): if n < 0 or n != int(n): raise ValueError('factorial input must be a count') <body as above> To do same with recursion, you have to write main function as a nested function to avoid useless doing check more than once. Conclusion: for linear processing of collections, use a while or for loop.
<compress stack>
While I do not see much in the idea. * Converting recursion to iteration compresses stack to 1 frame. * Slows down all computation for rare benefit. * Does not really scale very well. In most languages, factorial overflows long before there is a stack problem. To be realistic, consider linearly processing a billion character string with recursion versus iteration. * Recursion does not work with iterators as well as iteration. Iterators are one of Python's crown jewels. with open('terabyte.txt') as f: for c in chars(f): process(c) is the right idiom for independently processing the characters of a terabyte file. -- Terry Jan Reedy