Рекурсия внутри класса в питоне

Question

Я знаю, что это очень простой вопрос, и я нашел примеры кодов в Интернете, но я не могу понять, почему это работает.

Если нам нужно пройти через двоичное дерево в порядке предварительного заказа, один из способов сделать это (цитируется здесь http://interactivepython.org/courselib/static/pythonds/Trees/TreeTraversals.html) - использовать что-то вроде:

def preorder(self):
     print(self.key)
     if self.leftChild:
        self.leftChild.preorder()
     if self.rightChild:
        self.rightChild.preorder()

Я не понимаю, почему возможно сделать что-то вроде self.leftChild.preorder(). Если кто-то может указать мне правильное направление, я буду очень признателен.

EDIT:

Как указано в комментариях, я публикую полный код, над которым я работаю. Я получил это от firecode:

post_ordered_list = []
class BinaryTree:

    def __init__(self, root_data):
        self.data = root_data
        self.left_child = None
        self.right_child = None

    def postorder(self):
        if self.left_child:
            self.left_child.postorder()
        if self.right_child:
            self.right_child.postorder()
        post_ordered_list.append(self.data)
        return post_ordered_list


    def get_right_child(self):
        return self.right_child

    def get_left_child(self):
        return self.left_child

    def set_root_val(self, obj):
        self.data = obj

    def get_root_val(self):
        return self.data

Answer 1

Рекурсия имеет два шага: базовый случай и рекурсивный случай.Базовый случай останавливает рекурсию, но, насколько я понимаю из вашего поста, вы ищете, почему рекурсивный случай работает.Ключом к рекурсивному случаю является то, что следующий рекурс меньше того, который его вызвал.

Ваша функция предзаказа берет корень в качестве параметра.Когда вы в первый раз вызываете preorder, вы используете self в качестве параметра, что означает, что вы берете все дерево.Если у корня есть левый потомок, то следующим шагом будет рассмотрение левого поддерева.Корень левого поддерева - это левый дочерний элемент текущего корня, поэтому он передается в качестве параметра.Вы продолжаете двигаться вниз по левой стороне, пока есть левый ребенок.Рекурсия останавливается, когда нет левого дочернего элемента, и код переходит к правому дочернему оператору if для этого последнего узла.

Я мог бы продолжить, но не без смущения.(Надеюсь, я уже не сбиваю с толку!) Проверьте эту страницу в бинарном поиске, который является очень похожим действием.

Answer 2

В Python classInstance.methodName(params...) эквивалентно вызову метода methodName некоторого класса, с classInstance, переданным как self:

1. Определите, какой класс classInstance, который выможно получить с помощью type(classInstance) или classInstance.__class__ (ищите classInstance = Class(...) код создания экземпляра).
2. Определите, определяет ли класс methodName с self в качестве первого параметра.self, являющийся первым параметром, указывает, что это метод экземпляра, а не метод класса или статический метод (объяснение ссылки см. Ниже).Если такой метод существует, то вызовите его с self, равным classInstance, то есть эквивалентный вызов будет Class.methodName(classInstance, params...).
3. Если класс не определяет methodName, то найдите ближайшего предка, который это делает, следуя документации по наследованию , и сделайте то же самое.В этом случае эквивалентный вызов будет выглядеть следующим образом: ParentClass.methodName(classInstnace, params...).

Вот пример:

n4 = BinaryTree(4)
n5 = BinaryTree(5)
n3 = BinaryTree(3)
n3.left_child = n5
n3.right_child = n4
"""
  3
 /  \
4    5
"""

n3.postorder()
# result [5, 4, 3]

При вызове n3.postorder()

• self равно n3
• self.leftchild равно n5
• self.rightchild равно n4.

Когда выполняется n3.postorder(), следующая строка - self.left_child.postorder() и вызывает метод postorder с self.leftchild (т.е. n5) в качестве первого параметра (т. Е. "Self") из postorder.Следовательно, в контексте этого рекурсивного вызова:

• self равно n5
• self.leftchild равно None
• self.rightchild равно None,

Затем этот вызов метода завершается и выполняется следующая строка, self.right_child.postorder(), и это то же самое, что и выше, но с n4, поскольку мы вернулись в исходный контекст, где self.right_child это n4.

Подробная документация доступна по адресу: https://docs.python.org/3/tutorial/classes.html

Разница между экземпляром, классом и статическими методами: https://julien.danjou.info/guide-python-static-class-abstract-methods/

Answer 3

Рекурсия - это то, что трудно понять, начиная с программирования.Одна из вещей, которую вы должны осознать, это то, что, если вы правильно настроили базовые случаи (например, если self.left, self.right и т. Д.), Вы можете использовать функцию, над которой вы работаете, как если бы она былауже работает.

Давайте подумаем о примере подсчета всех узлов в дереве с помощью функции countNodes(): скажем, у нас есть узел x, который находится где-то в дереве.Когда x вызывается для подсчета всех узлов его поддерева, как он это делает?Помните, как я сказал, что мы должны притвориться, что функция countNodes() существует и что она уже работает?Что ж, давайте сделаем это.Х должен считать себя, потому что это узел.Следовательно, пока 1.После того, как он сосчитал сам, он должен сосчитать все узлы слева и все узлы справа.Таким образом, чтобы подсчитать узлы в дереве, начиная с любого узла x, мы вызываем countNodes () для левого и countNodes () для правого.

Таким образом, код будет выглядеть так:

def countNodes(self):
    count = 1
    if self.left: #Checking to see if we have a left subtree
        count += countNodes(self.left)
    if self.right: #Checking to see if we have a right subtree
        count += countNodes(self.right)
    return count

Итак, теперь, когда мы лучше понимаем рекурсию, давайте вернемся к вашему примеру.Мы хотим пройтись по дереву по предварительному заказу.По определению это означает, что мы должны сначала посетить наш узел.Затем мы видим, есть ли у нас левый узел для посещения.Если это так, мы пересекаем левые узлы в порядке предварительного заказа.Если у нас есть правильный узел, мы также просматриваем все это дерево в порядке предварительного заказа.

Крупнейшие выводы рекурсии:

1. Убедитесь, что у вас есть хорошие базовые случаи (например, если node.right == null)

2. Найти шаблон повторения.Вы можете использовать функцию в функции, как будто она уже построена, если у вас есть правильно работающие базовые случаи.

Надеюсь, это поможет!

Редактировать:

Чтобы объяснить ту часть себя, на которую я не смог ответить.Self представляет собой любой объект, называемый методом.Поэтому, если у нас есть узел x, с которым мы хотели бы выполнить предварительный обход, мы бы использовали x.preorder().Тогда в функции это будет выглядеть так:

def preorder(self): #self is whatever calls this function
    print(self.value) #whaver you want to print
    if self.left:
       self.left.preorder() #now in this function call, self will be self.left
   if self.right:
       self.right.preorder() #same idea here


root.preorder() #calling the function. Now self will be root.

Надеюсь, это прояснит некоторые вещи для вас.Извините, что сначала не понял проблему.Я надеюсь, что это отвечает на это.Дайте мне знать, если у вас есть дополнительные вопросы или вам нужно больше разъяснений.