CODEWITHSUNDEEP
pythonrecursiongraph
Amarth Gûl
Amarth Gûl

Reputation: 1082

Python recursion stopped unexpected

Briefly speaking, the recursion stopped halfway though everything else is fine.

The recursion function is shown below (The entire code can be found 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

The problem is that after a while's recursion, it stopped. The things that confused me are that:

  1. The input is fixed, but where it stops is not fixed. However, it always stopped at around 7000 times of invoke;
  2. All the failed recursions reaches checkpoint 1 but fails to reach checkpoint 2, and the recursion does not execute at all;
  3. It doesn't reach that maximum recursion time at all, I've set the max recursion as sys.setrecursionlimit(10**6)
  4. It runs pretty well on relatively small input (hundreds or thousands of nodes) but stuck on a large graph which has more than 800,000 nodes.

Which are driving me crazy, I can't see a reason why it doesn't work, no error, no stack overflow, just stopped, saying Press any key to continue ... as if it is finished. Anyone has a clue about what could possibly go wrong?

Upvotes: 1

Views: 1164

Answers (1)

Ante
Ante

Reputation: 5448

As documentation specifies:

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.

There is a script to check that limit.

You will have to implement non recursive DFS.

Upvotes: 2

Related Questions