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

Question

我正在尝试使用 DFS 实现 "subset" 算法。我发现以下两个程序都有效：

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 进行递归，但是当 branch递归结束，相同的元素从路径中删除，然后开始与以前相同的递归，但 PATH 列表中没有该元素。

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

('Path After Append : ', [1])

('Path After Append : ', [1, 2])

('Path After Append : ', [1, 2, 3])

('Path After Append : ', [1, 3])

('Path After Append : ', [2])

('Path After Append : ', [2, 3])

('Path After Append : ', [3])

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

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

How to understand the relationship between tail recursion and for loop in DFS

python

algorithm

recursion

depth-first-search