python - 递归函数如何在 'for loop' 中工作

Question

我是“递归函数”方面的新手。因此，我正在努力思考为什么我们使用递归函数以及递归函数是如何工作的，我认为我对此有相当好的理解。

两天前，我正在尝试解决最短路径问题。我有以下图表(在 python 中):

 graph = {'a': ['b', 'c'],
             'b': ['c', 'd'],
             'c': ['d'],
             'd': ['c'],
             'e': ['f'],
             'f': ['c']}

我只是想找到一条路径，而不是最短路径。所以，这是代码:

def find_path(graph,start,end,path=[]):
    path = path + [start]
    #Just a Test
    print(path)

    if start == end:
        return path

    if start not in graph:
        return None

    for node in graph[start]:
        if node not in path:
            new_path = find_path(graph,node,end,path)
        if new_path:
            #Just a test
            print(path)
            return new_path

print(find_path({'a':['b','c'],'b':['c','d'],'c':['d'],'d':['c'],'e':
['f'],'f':['c']},'a','d'))

我的起始顶点是“a”，结束顶点是“d”。

在第四行中，我只是打印了“路径”以查看路径的去向。

在第 17 行，我还打印了“路径”，再次只是为了测试。结果如下:

['a']
['a', 'b']
['a', 'b', 'c']
['a', 'b', 'c', 'd']
['a', 'b', 'c']
['a', 'b']
['a']
['a', 'b', 'c', 'd']

结果的前四行是代码第4行'print(path)'的结果。但是，第 5、6 和 7 行是代码第 17 行“print(path)”的结果。

我的问题是为什么路径列表每次都减少一个顶点？

我已经尝试了 2 天来寻找它的解决方案。我去过论坛，阅读有关递归的文档并观看视频。但是，运气不好。

如果有人能回答我将不胜感激。

Answer 1

这是因为递归会产生从“最内层”到“最外层”调用的结果。即第 17 行 print 语句从路径具有最多节点的最深递归级别出现。在该级别返回后，将打印下一个“向上”级别(路径中少一个节点)。请注意，您的 print 函数出现在 对 find_path 的递归调用之后。

您可以将其可视化如下:

find_path(..., path=['a'])  # Recursion level 1.
|
|   find_path(..., path=['a', 'b'])  # Recursion level 2.
|   |
|   |   find_path(..., path=['a', 'b', 'c'])  # Recursion level 3.
|   |   print(path)  # Prints ['a', 'b', 'c'].
|   |   return  # Return from level 3.
|   |
|   print(path)  # Prints ['a', 'b'].
|   return  # Return from level 2.
|
print(path)  # Prints ['a'].
return  # Return from level 1.

如果您希望单个(子)路径以“递增”顺序打印，那么您可以简单地将 print 函数放置在 before 递归调用 查找路径。

它是 new_path 变量，它保存递归找到的路径，而 path 只是保存到当前节点的路径。

顺便说一下，如果之前的 if 分支尚未进入，则 if new_path: 子句可能会失败，因为 new_path 未定义。