0
0 комментариев

Привет. У меня много раз вызывается рекурсивный dfs, после чего я получаю RuntimeError: maximum recursion depth exceeded in __instancecheck__. Такое ощущение, что происходит накопление рекурсивных вызовов за всё время работы программы. После превышения порога в сумме

sys.setrecursionlimit(20000)

прога падает. Как с этим бороться?

Для большей конкретики я приведу псевдокод моего алгоритма:

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) алгоритм выполняет больше итераций в цикле, но всё равно падает.

Таким образом, в некоторый момент возникает вышеуказанная ошибка. Замечу, что данная ошибка возникает у меня уже не первый раз. Возникает она в любом месте, где есть достаточное количество вызовов рекурсивных алгоритмов с большой глубиной рекурсии.

Замечу, что в коде нет терминального условия, но это не означает, что код будет выполняться бесконечно. Прокомментирую. Мы рассматриваем граф G(V, E). Будем перебирать вершины, начиная с любой. Каждую вершину мы будем помечать, если мы в ней были. Это делается следующей командой:

labels[current] = true

Для каждой вершины мы перебираем всех её соседей:

for neighbour in get_neighbours(current):

Если в вершине-соседе мы были, то в неё заходить не следует. Если же нет, то перейдём в нее. Проверка были мы там или нет осуществляется так:

if not (labels[neighbour]):

Далее переходим в вершину:

dfs(neighbour)

О конкретном алгоритме можно прочесть здесь. Но спешу заметить, что вопрос заключается не в алгоритме, а в принципах устройства python. Подробное описание кода я привёл лишь для того, чтобы снять сомнения в его работоспособности. Код взят лишь как пример и не более того!


Добавить комментарий