python - 如何理解DFS中尾递归和for循环的关系

Question

我正在尝试使用 DFS 实现“子集”算法。我发现以下两个程序都有效:

def DFS(nums, begin, path, res):
    res.append(path[:])

    for i in range(begin, len(nums)):
        path.append(nums[i])
        DFS(nums, i + 1, path, res)
        path.pop()


def DFS_2(nums, begin, path, res):
    if begin == len(nums):
        res.append(path[:])
        return

    path.append(nums[begin])
    DFS_2(nums, begin + 1, path, res) #choose the current element
    path.pop()
    DFS_2(nums, begin + 1, path, res) #not choose the current element

测试代码为:

nums = [i for i in range(1, 4)]
res = []
path = []

DFS_2(nums, 0, path, res)
print(res)

res2 = []
DFS(nums, 0, path, res2)
print(res2)

输出是:

DFS_2:[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

DFS: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

我能理解DFS_2，因为在每次递归中，我有两个选择——选择当前元素或不选择当前元素。但是我很难理解函数 DFS。如何理解 DFS 函数中的 for 循环？我的猜测是函数DFS_2中存在尾递归，这就是函数DFS和DFS_2等价的原因，但是我我不确定细节。

感谢任何提示。

Answer 1

好吧，函数 DFS 和 DFS_2 几乎是等价的。是的，您在函数 DFS_2 中有两个选择，这确实很容易看到，但在函数 DFS 中也有相同的两个选择。当程序在 PATH 列表中追加元素时，它会对该 PATH 进行递归，但是当递归的那个分支结束时，相同的元素将被删除从路径开始，然后开始与之前相同类型的递归，但 PATH 列表中没有该元素。

如果在 DFS 函数中每次追加后打印 PATH 列表，输出将是:

('追加后的路径:', [1])

('追加后的路径:', [1, 2])

('追加后的路径:', [1, 2, 3])

('追加后的路径:', [1, 3])

('追加后的路径:', [2])

('追加后的路径:', [2, 3])

('追加后的路径:', [3])

让我们看看，递归从第一个元素开始，并且进行了所有可能的排列。之后，进行了相同的递归，但其中没有第一个元素，依此类推，对列表中的所有元素进行了相同的操作。总而言之，列表中 i th 元素的每个递归都会看到其后的所有元素，并进行所有可能的排列。一开始，第一个元素被放入列表中，然后进行递归，第二个元素被放入，然后是第三个，然后递归跳水，删除第三个元素，然后是第二个元素，然后再次添加第三个元素，但是那里不再有第二个元素了。然后删除第二个元素并为第一个元素完成所有排列。所有这些都会发生同样的事情，但正如我所说，列表中 i th 元素的每个递归都只会看到其后的所有元素。