在递归函数中用尾递归替换for循环

Question

我试图让以下函数完全尾递归，例如得到那个讨厌的循环。原因是我试图轻松地将解决方案转换为涉及使用显式堆栈的迭代解决方案。请指教。

def permutations(A):
    P = []
    P2 = []
    permutations_recursive(A, [], P)
    permutations_tail_recursive(A, [], P2, 0)
    print(P2)
    return P

def permutations_recursive(first, last, perms):
    if len(first) == 0:
        perms.append(last)
    else:
        for i in range(len(first)):
            permutations_recursive(
                first[:i] + first[i+1:],
                last + [first[i]],
                perms)

Answer 1

关闭迭代模拟：

def permutations(A):
    P = []
    permutationsI(A, P)
    print(P)

def permutationsI(A, perms):
   stack = [(A, [])]
    while len(stack):
        first, last = stack.pop()
        if len(first):
            for i in range(len(first)):
                stack.append((first[:i] + first[i+1:],last + [first[i]]))
        else:
            perms.append(last)

permutations([1,2,3])
>>[[3, 2, 1], [3, 1, 2], [2, 3, 1], [2, 1, 3], [1, 3, 2], [1, 2, 3]]

Answer 2

一个完全递归的函数应该是：

def permutations_comp_recursive(first, last, perms, i):
    if len(first) == 0:
        perms.append(last)
    elif i == len(first):
        pass
    else:
        permutations_comp_recursive(first, last, perms, i+1)
        if first:
                permutations_comp_recursive(
                first[:i]+first[i+1:],
                last + [first[i]],
                perms, 0)

为了获得良好的表现，我推荐qazxsw poi。

编辑1：现在以下应该是尾递归的，使用列表推导。这在python中使用numpy solutions进行尾递归（最后2个参数被省略 - 结果作为返回值传递）：

workarount

这没有优化并使用循环。我不确定这个和上面没有循环的代码是否可以合并 - 可能会再次查看它。 itertools.permutations可用于此应用程序。