Бесконечная рекурсия DFS, но только если индекс вычисляется внутри рекурсивного шага ⇐ Python

[Anonymous]

Я застрял на пятом дне AOC этого года. Я стараюсь все это делать на питоне, чтобы этому научиться.
Короче, задача требует обхода графа. Я решил сделать это с помощью DFS.
Следующий фрагмент кода работает:

Код: Выделить всё

        nodes = [*self.adj_list.keys()]
node_states = [TopologicalStates.WHITE for _ in nodes]
predecessors = []

def visit_node(node_index, node):
node_states[node_index] = TopologicalStates.GRAY
adj_nodes = self.adj_list[node]
for adj_node in adj_nodes:
adj_node_index = nodes.index(adj_node)
if node_states[adj_node_index] == TopologicalStates.WHITE:
visit_node(adj_node_index, adj_node)
node_states[node_index] = TopologicalStates.BLACK
predecessors.append(node)

for (node_index, node) in enumerate([predecessor for (predecessor, successors) in self.adj_list.items() if node in successors]):
if node_states[node_index] == TopologicalStates.WHITE:
visit_node(node_index, node)

return predecessors

Однако, как только я попытаюсь удалить параметр node_index из visit_node и вместо этого определить новую переменную вверху visit_node, как показано ниже , я получаю бесконечную рекурсию!

Код: Выделить всё

        nodes = [*self.adj_list.keys()]
node_states = [TopologicalStates.WHITE for _ in nodes]
predecessors = []

def visit_node(node):
node_index = nodes.index(p)
node_states[node_index] = TopologicalStates.GRAY

adj_nodes = self.adj_list[node]
for adj_node in adj_nodes:
adj_node_index = nodes.index(adj_node)
if node_states[adj_node_index] == TopologicalStates.WHITE:
visit_node(adj_node)

node_states[node_index] = TopologicalStates.BLACK
predecessors.append(node)

for (i, p) in enumerate([predecessor for (predecessor, successors) in self.adj_list.items() if node in successors]):
if node_states[i] == TopologicalStates.WHITE:
visit_node(p)

return predecessors

Я начал сеанс отладки только для того, чтобы узнать, что node_states имеет начальное значение или, скорее, не сохраняется node_states[node_index] = TopologicalState.GRAY вызовы между вызовами рекурсии.
Как это возможно? Что я делаю неправильно? Это проблема «мого компьютера»?
Спасибо, любая помощь приветствуется.

Подробнее здесь: https://stackoverflow.com/questions/792 ... rsive-step