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

Question

我正在尝试使以下函数完全尾递归，例如将讨厌的 for 循环排除在外。原因是我试图轻松地将解决方案转换为涉及使用显式堆栈的迭代解决方案。请指教。def permutations(A):    P = []    P2 = []    permutations_recursive(A, [], P)    permutations_tail_recursive(A, [], P2, 0)    print(P2)    return Pdef 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)

为了获得良好的性能，我推荐numpy 解决方案。

编辑 1：现在以下应该是尾递归的，使用列表理解。这使用了python 中尾递归的解决方法（省略了最后 2 个参数 - 结果作为返回值传递）：

import itertools as it

class Recurse(Exception):

    def __init__(self, *args, **kwargs):

        self.args = args

        self.kwargs = kwargs

def recurse(*args, **kwargs):

    raise Recurse(*args, **kwargs)

def tail_recursive(f):

    def decorated(*args, **kwargs):

        while True:

            try:

                return f(*args, **kwargs)

            except Recurse as r:

                args = r.args

                kwargs = r.kwargs

                continue

    return decorated

@tail_recursive

def permutations_tail_recursive(first, last, direct=False):

    if len(first) == 0 or not all(first):

        return last

    else:

        l = len(first[0]) if direct else len(first)

        if last:

            return recurse([fi[:i]+fi[i+1:] for fi, i in it.product(first, range(l))],

                [last[j] + first[j][i] for j, i in it.product(range(len(last)), range(l))], True)

        else:

            return recurse([first[:i]+first[i+1:] for i in range(l)],

                [first[i] for i in range(l)], True)

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