Maximum recursion depth error

Question

I've been scouring the internet and haven't been able to find anything that would help. I'm running a basic dfs algorithm in python. My error is in the explore subroutine of dfs

def dfs(graph):
    for node in graph:
       if not node in visited:
          explore(graph, node)


def explore(graph, v):
   visited.append(v)
   adjNode = graph[v]
   for i in range(0, len(adjNode)):
       if not adjNode[i] in visited:
          explore(graph, adjNode[i])

visited is a list I'm using to keep track of visited nodes and graph is a dictionary that holds the graph. With a standard recursion limit of 1000 I get this error

  File "2breakDistance.py", line 45, in explore
    explore(graph, adjNode[i], cycles)
  File "2breakDistance.py", line 45, in explore
    explore(graph, adjNode[i], cycles)
  File "2breakDistance.py", line 45, in explore
    explore(graph, adjNode[i], cycles)
  File "2breakDistance.py", line 45, in explore
    explore(graph, adjNode[i], cycles)
  File "2breakDistance.py", line 41, in explore
    adjNode = graph[v]
RuntimeError: maximum recursion depth exceeded in cmp

First of all, I'm not quite sure why the error is occurring in adjNode = graph[v] since explore is the recursive call and adjNode is just list assignment.

But to deal with the recursion error, I increased the recursion limit with sys.setrecursionlimit(5000) I no longer get the error, but the program quits right before the adjNode = graph[v] line and exits with no error. It never even reaches the end of dfs so I'm not quite sure what's going on. Thanks for reading all this and for any help!

Sounds like it would best to rework your algorithm to be iterative rather than recursive. See http://blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html — Stephen Diehl, Jan 13 '14 at 01:28
Hmm, a bit meta perhaps, but should this question be tagged `tail-recursion` since [Python cannot recognize/optimize tail recursion](http://stackoverflow.com/questions/13591970/does-python-optimize-tail-recursion)? — kojiro, Jan 13 '14 at 01:30
Are you sure you're calling the right `explore` function? The exceptions says: `explore(graph, adjNode[i], cycles)` (3 arguments) and the one you're showing only shows two `def explore(graph, v):` — Paulo Bu, Jan 13 '14 at 01:34
`setrecursionlimit()` can be dangerous: the C stack can overflow then, and Python can do nothing to detect that or recover from random-ish errors that result from the C stack overflowing. Various kinds of data corruption are common then. "Early" termination is one pleasant ;-) way for that to manifest. — Tim Peters, Jan 13 '14 at 01:41
I am calling the right explore, I just edited my function a little and took out the cycles variable which was a book keeping variable to make it more understandable for the post. And I might try iterative instead and see if that helps with anything. And I had a feeling that something was still going wrong with the recursion when it terminated early! — kinsigne, Jan 13 '14 at 01:45
@kinsigne: If you simplify your code, post the stack trace from the simplified version. If your simplified code is unrunnable or doesn't produce an error, you simplified out something important. — user2357112, Jan 13 '14 at 02:07
It would be a good idea to make `visited` a set instead of a list. Just use `.add` instead of `.append`. The `in` test will be much faster then — John La Rooy, Jan 13 '14 at 03:43

davidism · Answer 1 · 2018-07-11T17:44:42.143

Python is not very good at recursion. It doesn't do any tail-call optimization, and runs out of frame space pretty quickly unless you manually change the recursion limit. It's also slower to lookup and call a function again instead of keeping code in a loop without recursion.

Try rewriting this without recursion instead. The error can be happening anywhere a new frame is created, not just where your recursive call is, which is why the error is happening there.

score 0 · Answer 2 · answered Jan 13 '14 at 02:03

def explore(graph, v):
    visited.append(v)
    adjNode = graph[v]
    for i in range(0, len(adjNode)):
        if not adjNode[i] in visited:
            explore(graph, adjNode[i])

This isn't making sense to me, what is in a node object? Why are you assigning adjNode back to the value of the node that you pass in. Is adjNode meant to be calling like a "GetConnections()" sort of function instead?

The logic currently feels like it should be this:

1. For each Node in Nodes:
      2. Add Node to visited
         Get Nodes Connections
         Explore SubNodes: 
             Go to 2.

Maximum recursion depth error

2 Answers2