使用 for 循环调用递归

Question

我无法解决这个问题：

def permut(array):
    if len(array) == 1:
        return [array]
    res = []
    for permutation in permut(array[1:]):
        for i in range(len(array)):
            res.append(permutation[:i] + array[0:1] + permutation[i:])
    return res

特别是 for 循环的第一行 - 树会是什么样子？我什至无法获得与我正在绘制的函数所做的结果相同的结果。任何帮助将不胜感激

Answer 1

递归“树”实际上只是一条路径。递归调用只有一处

算法基于这个思路：

如果我们知道比数组短一个元素的所有排列，那么我们可以使用这些排列来推导当前数组的所有排列：只需在所有这些排列的所有可能位置添加被排除的元素。

递归函数的基本情况是数组只有一个元素。在那种情况下，只有一个排列，即数组本身。

所以让运行输入 [1, 2, 3] 的代码：

外部 for 循环进行递归调用，将 [2, 3] 作为参数传递给它。

在此嵌套执行中：

外部 for 循环进行递归调用，将其作为参数传递给 [3]。我们知道这是基本情况，因此我们得到 [[3]] 作为 return 值。请注意，这是一个列表列表。

外部 for 循环迭代两次，在 [3] 的索引 0 和索引 1 处“注入”2，以便我们得到 [2, 3] 和 [3, 2] 作为第一个结果，并附加到 res.

res 被 returned 给调用者，即 [[2, 3], [3, 2]]

外循环执行了3次。每次在递归调用的每个结果中的不同位置注入 1。递归调用的第一个结果是 [2, 3]。在三个可能的位置注入 1，得到 [1, 2, 3]、[2, 1, 3] 和 [2, 3, 1]，它们被添加到 res。然后递归结果中的第二个子列表以相同的方式处理，所以我们得到 [1, 3, 2], [3, 1, 2] 和 [3, 2, 1]，它们也被添加到res.

备注：

您的代码将基本情况标识为具有一个元素的数组。这是一个缺点，因为这意味着当您向它传递一个空列表时，该函数将运行进入堆栈溢出错误。

使用 for 循环调用递归

Calling recursion with a for loop

python

tree

recursion

for-loop

permutation