Python рекурсивная функция для создания родового c дерева

Question

Я пытаюсь создать дерево с n дочерними элементами для каждого узла. Проблема в том, что когда я пытаюсь реализовать это с помощью рекурсивной функции, я заканчиваю несколькими рекурсивными вызовами, поэтому у меня не может быть одного оператора return, следовательно, None в качестве конечного результата.

Вот мой кусок кода:

def recursive_func(tree, n):
    if n == 0:
        return tree
    else:
        permutations = get_permutations()
        for permutation in permutations:
            child_tree = recursive_func(Tree(permutation), n-1)
            tree.addChild(child_tree)

get_permutations() дает список дочерних деревьев для создания. У меня также есть класс Tree со значением узла и списком дочерних элементов.

Вот класс дерева:

class Tree:
    def __init__(self, result):
        self.node = node
        self.children = []

    def addChild(self, tree):
        self.children.append(tree)

Это, вероятно, ошибка ладьи ie в дизайн моей проблемы, но я был бы рад получить помощь.

Answer 1

TLDR: Поскольку вы используете результат recursive_func, он всегда должен return его tree.

---

recursive_func имеет три важных момента для этой проблемы:

def recursive_func(tree, n):
    if n == 0:
        return tree  # 1.
    else:
        permutations = get_permutations()
        for permutation in permutations:
            child_tree = recursive_func(Tree(permutation), n-1)  # 2.
            tree.addChild(child_tree)
    # 3.

Теперь 1. определяет, что функция иногда возвращает Tree. Это соответствует 2., который всегда ожидает, что функция вернет Tree. Однако оба конфликтуют с 3., который неявно возвращает None, когда вторая ветвь завершена.

Поскольку первая ветвь пуста, кроме return, оба 1. и 3. могут свернуть на один путь, который всегда возвращает Tree.

def recursive_func(tree, n):
    if n > 0:
        permutations = get_permutations()
        for permutation in permutations:
            child_tree = recursive_func(Tree(permutation), n-1)
            tree.addChild(child_tree)
    return tree