1

I am implementing Depth-First Search algorithm to get strongly connected components of a graph having a very large number of nodes (upwards of 800,000).

When running, I get the following error:

RecursionError: maximum recursion depth exceeded in comparison

To solve this, I used help of the sys.setrecursionlimit(numNodes) function. When doing this, the IDLE begins to execute the code, but then restarts automatically without giving any output.

Based on a quick web search (for example), I think its because IDLE exceeded the memory limit when recursing through so many nodes.

For numNodes = 20000, sys.setrecursionlimit(3000) does the trick

For numNodes = 40000, sys.setrecursionlimit(5000) does the trick

For numNodes = 80000, sys.setrecursionlimit(5000) restarts the IDLE. (NOTE here, it doesn't show RecursionError, but restarts the IDLE only)

DOUBT : What is the maximum value of the limit for sys.setrecursionlimit(limit) that I can set for my platform?

UPDATE : Other, similar questions on stack overflow ask how to change the value or what is maximum recursion depth. I need to understand what the maximum possible value of the "limit" is. sys.getrecursionlimit() would give me whatever "limit" has been currently set.

Anshul Jindal
  • 61
  • 1
  • 10
  • 1
    Related: [What is the hard recursion limit for Linux, Mac and Windows?](https://stackoverflow.com/questions/2917210/python-what-is-the-hard-recursion-limit-for-linux-mac-and-windows) – Georgy Aug 05 '19 at 17:56

1 Answers1

0

You already have found an answer to your problem, but you still don't have an answer as to how to get around the recursion limit.

The simple approach is to maintain your own stack. That can be done like this for depth first.

todo = [starting, stuff]
while 0 < len(todo):
    task = todo.pop()
    do work
    todo.extend(future_tasks)

In this form, switching from DFS to BFS requires switching from a stack to a queue. Which in Python is easy:

todo = [starting, stuff]
while 0 < len(todo):
    task = todo.pop(0)  # CHANGED HERE
    do work
    todo.extend(future_tasks)
btilly
  • 43,296
  • 3
  • 59
  • 88