Python递归意外停止

Question

简单地说，递归停止了一半，尽管其他一切都很好。在

递归函数如下所示（整个代码可以找到here）：

def DFS(graph, startNode = 0):
    global nodesProcessed; global explored; global finishingTime
    explored[startNode] = True
    currentLeader = startNode

    if startNode in graph:
        for neighbor in graph[startNode]:
            if not explored[neighbor]:
                #checkpoint 1
                DFS(graph, neighbor)
                #checkpoint 2
    else: return currentLeader

    nodesProcessed += 1
    finishingTime[startNode] = nodesProcessed
    return currentLeader

问题是经过一段时间的递归后，它停止了。让我困惑的是：

1. 输入是固定的，但停止的位置不是固定的。但是，它总是在大约7000次调用时停止
2. 所有失败的递归到达checkpoint 1，但未能到达checkpoint 2，并且该递归根本不执行
3. 它根本没有达到最大递归时间，我将最大递归设置为sys.setrecursionlimit(10**6)
4. 它在相对较小的输入（成百上千个节点）上运行得很好，但却停留在一个拥有超过80万个节点的大型图上。在

这让我抓狂，我看不出它为什么不工作，没有错误，没有堆栈溢出，只是停止，说Press any key to continue ...好像它完成了。有人知道可能出什么问题吗？在

Answer 1

正如documentation指定的那样：

The highest possible limit is platform-dependent. A user may need to set the limit higher when they have a program that requires deep recursion and a platform that supports a higher limit. This should be done with care, because a too-high limit can lead to a crash.

有一个script来检查这个限制。在

您必须实现非递归DFS。在