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 1

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.