为什么递归代码不打印 None 分支？

Question

我做了一个有效的递归函数，这通常是人们想要的:)

但是，当它遍历 "tree" 个选项时，我想知道为什么它不打印 None 个分支。

图表：

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

函数：

def find_path(self, start_vertex, end_vertex, path=[]):
    graph = self.__graph_dict
    path.append(start_vertex)

    if end_vertex == start_vertex:
        return path

    for neighbour in graph[start_vertex]:
        if neighbour not in path:   
            extended_path = self.find_path(neighbour, end_vertex, path)

            if extended_path:
                return extended_path

    return None

我不明白的情况是邻居在路径中并且它return None。

print(self.find_path(a,f))
>> ['a', 'c', 'b', 'e', 'g', 'f']

Answer 1

因此，据我从评论中了解到您的问题是："why are wrong paths not printed?"。答案是被淘汰了。

例如，查看的第一条路径是潜在循环a-c-a-c-a-c，但由于短路，它从未完全迭代：

if neighbour not in path:   # prevents loops

如果您移除从 a 到 c 的传球，您会看到死胡同 return None。在找到正确的路径之前，您目前没有死胡同。

至于你的代码，我相信你想为每个递归框架创建一个新列表，因为列表是可变的并且你可能通过两个独立的框架改变 path 列表导致不一致：

graph = self.__graph_dict
# path.append(start_vertex) # this was wrong
path = path += [start_vertex]

这样会为每个选项生成一个新列表。您在答案中的解决方案：

['a', 'c', 'b', 'e', 'g', 'f']

实际上是错误的，应该是：

['a', 'c', 'e', 'g', 'f']

Answer 2

它从未达到 return None。

我不明白的是，只有在正确的条件下它才会继续遍历树。

在 a 和 b 处，循环继续循环，直到它定义了一个 extended_path。如果没有这样的路径，只有这样，它 returns None.

为什么递归代码不打印 None 分支？

Why a recursive code does not print the None branches?

python

tree

recursion