Операции рекурсии и возврата Python

Я новичок в Python и рекурсивных функциях в целом, поэтому прошу простить мое невежество.

Я пытаюсь реализовать двоичное дерево поиска в Python и иметь следующий метод вставки (взятый из класса):

def insert(self, key, root=None):
    '''Inserts a node in the tree'''
    if root == None:
        root = self.root
    if root.key == None:
        self._update(root, key)
        return 0
    else:
        tmp = root
        if key > tmp.key: # we work with the right subtree
            self.insert(key, root=tmp.right)
        elif key < tmp.key: # we work with the left subtree
            self.insert(key, root=tmp.left)
        else: # key already exists
            return 0

Я не уверен, что это разборчиво, но оно проходит дерево до тех пор, пока оно не достигнет значения None и обновит node с помощью ключа для вставки.

Теперь этот метод работает красиво и правильно создает BST с нуля. Но есть проблема с операторами return, поскольку он возвращает только 0, если рекурсия не выполняется.

>>> bst.insert(10)
0
>>> bst.insert(15)
>>> bst.root.right.key
15
>>>

"Вставка" корневого ключа снова возвращает 0 (из строки 15), как это должно быть.

>>> bst.insert(10)
0

Я не могу понять, почему это происходит. Если я поставлю оператор печати в строке 6, он будет выполняться правильно, но он просто не вернет ничего после первой вставки. Почему это? (Я уверен, что у меня отсутствует основная информация о Python и рекурсии)

Спасибо за вашу помощь,

Иван

P.S.: Я читал, что рекурсия - это не лучший способ реализовать BST, поэтому я рассмотрю другие решения, но я хотел бы знать ответ на этот вопрос, прежде чем двигаться дальше.

Ответы

Ответ 1

В рекурсивных строках вы ничего не возвращаете. Если вы хотите, чтобы он возвращал 0, вы должны заменить их такими строками, как:

return self.insert(key, root=tmp.left)

вместо

self.insert(key, root=tmp.left)

Ответ 2

Вы находитесь внутри функции и хотите вернуть значение, что вы делаете? Вы пишете

def function():
    return value

В вашем случае вы хотите вернуть значение, возвращаемое вызовом функции, поэтому вам нужно сделать.

def function():
    return another_function()

Однако вы делаете

def function():
    another_function()

Почему вы думаете, что это должно сработать? Конечно, вы используете рекурсию, но в таком случае вы должны помнить Zen of Python, который просто говорит:

Особые случаи не являются достаточно сложными, чтобы нарушать правила.