递归函数如何在'for循环'中工作

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

首先我要解释一下回溯的含义。我也在这里发布了这个答案。

递归意味着从同一函数内调用该函数。现在发生的情况是，当函数遇到对自身的调用时......想象一下，打开一个新页面，并且控制权从旧页面转移到这个新页面到函数的开头，当函数在此再次遇到调用时新页面，旁边会打开另一个页面，这样新页面就会不断在旧页面旁边弹出。请注意，所有局部变量仅在其各自页面的范围内。也就是说，如果您想访问上一页中的值，您可以将其传递给参数中的函数或将变量设置为全局变量。

返回的唯一方法是使用 return 语句。当函数遇到它时，控件从调用它的同一行上从新页面返回到旧页面，并开始执行该行下方的任何内容。这就是回溯开始的地方。为了避免在数据填满时再次输入数据等问题，您通常需要在每次调用函数后添加一个 return 语句。

现在在你的代码中，

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)  <---- when function returns it will start executing from here again.
        if new_path:
            #Just a test
            print(path)
            return new_path

请注意，您的path变量不是全局变量。这是当地人。这意味着每次您调用它时都会重置。为了避免这种情况，您将在函数参数中再次传递路径值（在最后一个参数中）。

因此，最终当函数在找到后返回时，d它会返回到路径变量仅包含在其中的先前状态a, b, c。这就是你打印出来的内容。

编辑：-以防万一有人反对，我对使用页面的递归的解释纯粹是非技术性的，如果你想知道它是如何发生的，那么你必须阅读激活记录以及它如何将所有状态推送到堆栈上