这是我解决这个问题的代码:
def nfsmaccepts(current, edges, accepting, visited):
print ('iteration', current, ''.join([i[1] for i in visited]))
if current in accepting:
print ('accepted')
return ''.join([i[1] for i in visited])
else:
for edge in edges:
if edge not in visited and current == edge[0]:
print (edge, ' matched')
visited.append(edge)
for i in edges[edge]:
if nfsmaccepts(i, edges, accepting, visited) is not None:
print (edge, i, ' chosen')
return nfsmaccepts(i, edges, accepting, visited)
else:
visited = visited[:-1]
结果如下:
print(nfsmaccepts(1, edges, accepting, []))
iteration 1
(1, 'a') matched
iteration 2 a
(2, 'a') matched
iteration 2 aa
iteration 3 a
(3, 'b') matched
iteration 4 ab
(4, 'c') matched
iteration 5 abc
accepted
(4, 'c') 5 chosen
iteration 5 abc
accepted
(3, 'b') 4 chosen
iteration 4 abc
None
我无法弄清楚为什么程序继续运行 for 循环并在明显达到递归函数的终端调用时返回 None 。请帮忙!