[Python-ideas] Idea: Compressing the stack on the fly

Sun May 26 22:08:00 CEST 2013

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