0

这是我解决这个问题的代码：

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 。请帮忙！

4

1 回答 1

1

if当您从语句中调用您的函数时，您的“已接受”状态就会出现：

if nfsmaccepts(i, edges, accepting, visited) is not None

然后继续打印(4, 'c') 5 chosen。之前的迭代也是如此，所以你从迭代 4 中再次调用它，同时打印(3, 'b') 4 chosen。

也许您打算只在那里调用一次该函数并在测试和返回之前存储结果？

accepts = nfsmaccepts(i, edges, accepting, visited)
if accepts is not None:
    print (edge, i, ' chosen')
    return accepts
于 2013-03-05T17:14:18.973 回答