Python рекурсия и операторы возврата

Question

Я довольно плохо знаком с 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, и не обновит узел ключом для вставки.

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

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

«Вставка» корневого ключа снова возвращает 0 (из строки 15) так, как должно.

>>> bst.insert(10)
0

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

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

Иван

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

Answer 1

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

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

вместо

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

Answer 2

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

def function():
    return value

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

def function():
    return another_function()

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

def function():
    another_function()

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

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