CODEWITHSUNDEEP
pythontail-recursion
kinsigne
kinsigne

Reputation: 93

Maximum recursion depth error

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!

Upvotes: 0

Views: 820

Answers (2)

davidism
davidism

Reputation: 127210

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.

Upvotes: 1

Aidan
Aidan

Reputation: 767

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.

Upvotes: 0

Related Questions