Рекурсивный алгоритм. Переполнение стека

#python #алгоритм #рекурсия

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

Ответы

Ответ 1

Посмотрите внимательно на Вашу функцию

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


Я удалю несколько часть строк, что бы показать явную проблему

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


переменная current не меняется внутри функции. И получается, что значение фукнции
зависит от значения функции. Такая рекурсия никогда не закончится. Именно для этого
в большинстве интерпретаторов есть защита от таких бесконечных рекурсий - лучше программисту
сразу намекнуть, что его код подозрительный.

Что делать? Исправить код. Как минимум, думаю нужно изменить параметр. А вот как
именно - это только Вы знаете.


Ответ 2

Может вам надо переписать DFS на нерекурсивную версию? Я в алгоритмах 0 но  https://stackoverflow.com/a/21508819/1717474
вот ответ на ваш вопрос по моему, а если вам надо времена входа/выхода "корректные"
то все сложнее: https://stackoverflow.com/a/43906820/1717474