Maximum recursion depth exceed while doing DFS in python3, not solved by increasing limit

Question

I wrote up a program which counts the size of the 5 largest SCC's in a given graph. The number of nodes in the graph is 875714. Following is the basic DFS code I'm using in the problem. (Both functions are methods in a class)

def DFSloop(self):
    exp = [False] * (self.size + 1)

    for i in range(1,(self.size + 1)):
        if exp[i] == False:
            self.DFS(i, exp) 

def DFS(self, s, exp):
    exp[s] = True
    for vertex in self.g[s]:
        if exp[vertex] == False:
            self.DFS(vertex, exp)

Basically DFS has to recurse a lot as number of nodes and edges is huge. It showed the following error even after setting the recursion limit to 10,000

RuntimeError: maximum recursion depth exceeded in cmp

Then upon increasing the limit to 100,000, it showed:

Segmentation fault: 11

And the system crashed. Any help in overcoming the situation?

Tarik · Accepted Answer · 2020-05-15 22:37:09Z

1

I overcame a similar issue by using a stack instead of using recursion.

Example:

def fib(n):
    stack = [n]
    s = 0
    while len(stack) > 0:
        n = stack.pop()
        if n < 2:
            s += n
        else:
            stack.append(n-1)
            stack.append(n-2)

    return s

edited May 15, 2020 at 22:37

answered May 15, 2020 at 22:29

Tarik

11.2k2 gold badges31 silver badges47 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Mulan Over a year ago

who said imperative programs cannot be beautiful?

Collectives™ on Stack Overflow

Maximum recursion depth exceed while doing DFS in python3, not solved by increasing limit

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related