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

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

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

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

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

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

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

В 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) в качестве первого параметра (т. е. «я») 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/