python – Recursive algorithm. Stack overflow

Question:

During the execution of my algorithm, recursive dfs is called many times, after which I get

RuntimeError: maximum recursion depth exceeded in instancecheck

It seems that there is an accumulation of recursive calls for the entire duration of the program. After exceeding the threshold in the amount

sys.setrecursionlimit(20000)

the program crashes. How to deal with this?

I will give a pseudocode of my algorithm:

func dfs(current):
    global labels
    labels[current] = true
    for neighbour in get_neighbours(current):
        if not (labels[neighbour]):
            dfs(neighbour)
        do_smth()

for item in range(0, n):
   dfs(item) // Происходит несколько итераций цикла, после чего прога падает. При увеличении значения n в sys.setrecursionlimit(n) алгоритм выполняет больше итераций в цикле, но всё равно падает.

So at some point the above error occurs. Note that this is not the first time I have encountered this error. It occurs in any place where there are a sufficient number of calls to recursive algorithms with a large recursion depth.

Note that there is no terminal condition in the code, but this does not mean that the code will execute indefinitely. I will comment. We consider the graph G (V, E). We will iterate over the vertices, starting from any. We will mark each vertex if we were in it. This is done with the following command:

labels[current] = true

For each vertex, we iterate over all of its neighbors:

for neighbour in get_neighbours(current):

If we were at a neighboring vertex, then we should not enter it. If not, then go to it. The check whether we were there or not is carried out as follows:

if not (labels[neighbour]):

Next, go to the top:

dfs(neighbour)

You can read about a specific algorithm here . But I hasten to note that the question is not in the algorithm, but in the principles of the python device. I gave a detailed description of the code only to remove doubts about its performance. The code is taken only as an example and nothing more.

Answer:

Take a close look at your function

func dfs(current):
    global labels
    labels[current] = true
    for neighbour in get_neighbours(current):
        if not (labels[neighbour]):
            dfs(current)
        do_smth()

I will remove some of the lines to show an obvious problem.

func dfs(current):
    #
    dfs(current)
    #

the current variable does not change inside the function. And it turns out that the value of the function depends on the value of the function. This kind of recursion will never end. That is why most interpreters have protection against such endless recursions – it is better for the programmer to immediately hint that his code is suspicious.

What to do? Correct the code. At the very least, I think the parameter needs to be changed. But how exactly – only you know.

Scroll to Top