如何理解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。如何理解for函数中的DFS循环？我的猜测是函数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个元素的每个递归都会看到自身之后的所有元素并执行所有可能的排列。在开始时，第一个元素放在列表中，然后进行递归，第二个放置，然后是第三个，然后递归向下，擦除第三个元素，然后第二个元素再次添加第三个元素，但不再有第二个元素。然后擦除第二个元素并对第一个元素进行所有排列。所有这些都发生了同样的事情，但正如我所说的，列表中第i个元素的每个递归都只能看到所有元素。