如何将此非尾递归函数转换为循环或尾递归版本? [英] How to convert this non-tail-recursion function to a loop or a tail-recursion version?

问题描述

我对这个很好奇很久了.人类创建一个非尾递归函数来搞复杂的事情真的很简单很优雅，但是速度很慢，很容易达到Python递归的极限:

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

那么，如何将 moves_three 更改为尾递归一或循环(更好)?更重要的是，有没有什么文章可以讨论这个?谢谢.

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.

推荐答案

即使使用迭代形式，这也不会变得更快.问题不在于递归限制；你仍然比递归限制低一个数量级.问题是输出的大小是 O(2^n).对于 n=100，您必须构建一个包含大约 1000 亿个元素的元组.你如何构建它并不重要；你永远做不完.

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)

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

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.

这篇关于如何将此非尾递归函数转换为循环或尾递归版本?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！