How to convert this non-tail-recursion function to a loop or a tail-recursion version?
Question: I've been curious for this for long. It is really very easy and elegant for
human to create a non-tail-recursive function to get something complicated,
but the speed is very slow and easily hit the limit of Python recursion:

    
    
    def moves_three(n, ini=0, med=1, des=2):
        '''give a int -> return a list '''
        if n == 1:
            return ((ini,des),)
        return moves_three(n-1, ini=ini, med=des, des=med) + \
               ((ini, des),) + \
               moves_three(n-1, ini=med, med=ini, des=des)
    
    if __name__ == '__main__':
        moves_three(100) # may be after several hours you can see the result.
        len(moves_three(10000)) 
    

So, how to change `moves_three` to a tail recursion one or a loop (better)?
More important, are there any essays to talk about this? Thanks.


Answer: Even with an iterative form, this isn't going to get any faster. The problem
isn't the recursion limit; you're still an order of magnitude below the
recursion limit. The problem is that the size of your output is `O(2^n)`. For
`n=100`, you have to build a tuple of about a thousand billion billion billion
elements. It doesn't matter how you build it; you'll never finish.

If you want to convert this to iteration anyway, that can be done by managing
state with an explicit stack instead of the call stack:

    
    
    def moves_three(n, a=0, b=1, c=2):
        first_entry = True
        stack = [(first_entry, n, a, b, c)]
        output = []
        while stack:
            first_entry, n1, a1, b1, c1 = stack.pop()
            if n1 == 1:
                output.append((a1, c1))
            elif first_entry:
                stack.append((False, n1, a1, b1, c1))
                stack.append((True, n1-1, a1, c1, b1))
            else:
                output.append((a1, c1))
                stack.append((True, n1-1, b1, a1, c1))
        return tuple(output)
    

Confusing, isn't it? A tuple `(True, n, a, b, c)` on the stack represents
entering a function call with arguments `n, a, b, c`. A tuple `(False, n, a,
b, c)` represents returning to the `(True, n, a, b, c)` call after
`moves_three(n-1, a, c, b)` ends.

