Рекурсивный поиск по дереву прекращается слишком рано

Question

Я новичок как в Python, так и в рекурсии, поэтому мне, возможно, не удалось найти какой-то соответствующий вопрос, но я не видел именно этого. У меня есть задача найти количество детей для каждого имени в следующем списке:

parents = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'V', 'W', 'X', 'Y', 'Z']

У меня есть следующая структура графа с родителями вверху и детьми внизу ( как в формате dict, так и в виде диаграммы). Каждая буква считается своим собственным дочерним элементом, поэтому минимальное количество дочерних элементов равно одному.

data = {'G': ['F'], 'A': [], 'B': ['A'], 'C': ['A'], 'D': ['B', 'C'], 'E': ['D'], 'F': ['D'], 'X': [], 'Y': ['X', 'A'], 'Z': ['X'], 'V': ['Z', 'Y'], 'W': ['V']}

     A   X
    /|\ / \
   B C Y   Z
    \|  \ /
     D   V
    / \   \
   E   F   W
        \
         G

Я знаю правильные ответы на вопрос

Node   Correct   My_answers
A       10          10
B       5           1          Incorrect
C       5           5
D       4           4
E       1           1
F       2           2
G       1           1
V       2           2
W       1           1
X       5           2          Incorrect
Y       3           3
Z       3           1          Incorrect

Я попытался разделить решение на две разные функции, а затем распечатайте ответы, используя простой l oop. is_parent() проверяет, является ли par родительским, если cld, и, если я не ошибаюсь, это означает, что cld является дочерним элементом par. Я сделал это из-за формата ввода. Затем у меня есть child_count(), который просто выплевывает счетчик, перебирая все имена и проверяя, имеет ли данный потенциальный дочерний элемент (pot_child) par в качестве своего родителя. Я подозреваю, что у меня проблема в is_parent(), которая выплевывает False , прежде чем он тщательно проверит все ветви дерева , что приводит к тому, что количество дочерних элементов ниже истинных.

Вот полный код, который я написал, данные и родители определены выше.

def is_parent(cld, par, data):
    if cld == par:
        return True
    else:
        for par_2 in data[cld]:
            x = is_parent(par_2,par,data)
        if len(data[cld]) == 0:
            x = False
    return x
def child_count(par, data):
    cnt = 0
    for pot_child in data:  # for each potential child
        cnt += 1 if is_parent(pot_child, par, data) else 0
    return cnt


for parent in parents:
    print(parent,":",child_count(parent, data))

Извините за слишком длинное введение в вопрос, но суть того, что я пытаюсь задать, заключается в вдвойне. Во-первых, подходит ли мой общий подход к проблеме (две функции, а затем al oop), есть ли более быстрая и удобочитаемая альтернатива? Во-вторых, как сделать так, чтобы мой алгоритм рекурсивного поиска не останавливал поиск слишком рано (я пробовал визуализатор, но он останавливается после 1000 шагов, что недостаточно для моего алгоритма)? Как убедиться (в общем), что рекурсивный алгоритм не останавливается слишком рано. * Спасибо заранее!

Answer 1

Ошибка здесь:

def is_parent(cld, par, data):
    if cld == par:
        return True
    else:
        for par_2 in data[cld]:
            x = is_parent(par_2,par,data) # <=== if x is True, return True!
            if x: break # <== quick fix
        if len(data[cld]) == 0:
            x = False
    return x

Вход в систему прост. Если одна из «ветвей» графа ведет к родителю, результатом будет True независимо от других ветвей

После некоторой очистки:

def is_parent(cld, par, data):
    return cld == par or any(is_parent(par_2,par,data) for par_2 in data[cld])

Ориентированный граф не должен содержать циклов. В заголовке упоминается «дерево», даже если данные примера не являются строго деревом, но это l oop бесплатно. Если бы циклы были разрешены, потребовался бы набор посещаемых узлов, чтобы остановить бесконечную рекурсию.

(прошу прощения за то, что не ответил на вопрос, как вообще писать рекурсивные функции и какие ресурсы рекомендуются)