如何将这个非tailrecursion函数转换为循环或tailrecursion版本？

Question

我对此好奇很久了。对于人类来说，创建一个非尾部递归函数来获取复杂的东西确实非常容易和优雅，但是速度非常慢，很容易达到Python递归的极限：

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)) 

那么，如何将moves_three更改为尾部递归或循环（更好）？更重要的是，有什么文章可以讨论这个问题吗？谢谢。在

Answer 1

即使使用迭代形式，也不会更快。问题不在于递归限制；你仍然比递归限制低一个数量级。问题是输出的大小是O(2^n)。对于n=100，您必须构建一个由1000亿个元素组成的元组。不管你怎么建造它，你永远都不会完成。在

如果要将其转换为迭代，可以通过使用显式堆栈（而不是调用堆栈）管理状态来完成：

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)

令人困惑，不是吗？堆栈上的元组(True, n, a, b, c)表示输入带有参数n, a, b, c的函数调用。元组(False, n, a, b, c)表示在moves_three(n-1, a, c, b)结束后返回(True, n, a, b, c)调用。在