Блог

Главная - Вопросы по программированию - Операторы рекурсии и возврата

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

#python #numpy

Вопрос:

Я довольно новичок в 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 и рекурсии)

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

Иван

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

Комментарии:

1. Я не уверен, что, по вашему мнению, он должен возвращать, кроме 0. Можете ли вы показать, чего вы ожидаете?

2. @imiric: Я думаю, что вы получили несколько полезных советов от других, но я также хотел бы отметить, что ваш инстинкт опустить оператор возврата может подсказать, что вы думаете выражениями, а не утверждениями. Если да, то, возможно, вам подойдет такой язык, как Схема. Вам, конечно, не нужно отказываться от Python, но держите свой разум открытым для функциональных языков программирования.

Ответ №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()

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

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

Ответ №3:

Вам нужен оператор return в вашем рекурсивном случае. Попробуйте эту настройку.

 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
            return self.insert(key, root=tmp.right)
        elif key < tmp.key: # we work with the left subtree
            return self.insert(key, root=tmp.left)
        else: # key already exists
            return 0
Метки: