Еще примеры рекурсии

Настоящие преимущества рекурсии становятся очевидны, когда мы сталкиваемся с задачами, для которых трудно написать итеративные решения. Например, посмотрим на бинарные деревья. Бинарное дерево - это ветвящаяся структура, где есть узлы, и в каждом узле структура ветвится максимум на две дочерние ветви со своими узлами. Бинарное дерево могло бы выглядеть так (информатику часто считают ветвью естественных наук, но наше понимание деревьев немного перевернутое, как вы заметите):

Бинарные деревья как минимум теоретически должны легко обрабатываться рекурсивно: если мы хотим выполнить какую-то операцию над каждым узлом дерева, нашему алгоритму нужно просто

1. Обработать текущий узел
2. Вызвать себя для дочернего узла слева
3. Вызвать себя для дочернего узла справа

Как видно на изображении выше, и левое, и правое "поддеревья" сами являются полноценными бинарными деревьями, а единственный узел, остающийся вне рекурсивных вызовов, - это родительский узел, который обрабатывается на шаге 1 перед рекурсивным вызовом функции. Поэтому мы можем быть уверены, что когда выполнение функции закончится, каждый узел будет посещен ровно один раз.

Итеративная версия обхода бинарного дерева была бы гораздо сложнее, поскольку нам пришлось бы как-то отслеживать все узлы, которые мы уже посетили. Те же принципы верны для всех вычислительных древовидных структур, не только для бинарных.

Бинарное дерево легко смоделировать и в коде Python. Нужно написать только определение класса для одного узла. У него есть атрибут value и атрибуты для левого и правого дочерних узлов:

class Node:
    """ The class represents a single node in a binary tree """
    def __init__(self, value, left_child:'Node' = None, right_child:'Node' = None):
        self.value = value
        self.left_child = left_child
        self.right_child = right_child

Теперь предположим, что мы хотим смоделировать следующее дерево:

Этого можно добиться следующим кодом:

if __name__ == "__main__":
    tree = Node(2)

    tree.left_child = Node(3)
    tree.left_child.left_child = Node(5)
    tree.left_child.right_child = Node(8)

    tree.right_child = Node(4)
    tree.right_child.right_child = Node(11)

Рекурсивные алгоритмы для бинарных деревьев

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

Аргументом функции печати является корневой узел бинарного дерева. Это узел на самом верху в нашей иллюстрации выше. Все остальные узлы являются дочерними для этого узла:

def print_nodes(root: Node):
    print(root.value)

    if root.left_child is not None:
        print_nodes(root.left_child)

    if root.right_child is not None:
        print_nodes(root.right_child)

Функция печатает значение узла, переданного как аргумент, а затем вызывает саму себя для левого и правого дочерних узлов, если эти узлы определены. Это очень простой алгоритм, но он эффективно и надежно проходит все узлы дерева независимо от размера дерева. Важно, что ни один узел не посещается дважды. Каждое значение печатается только один раз.

Если передать функции корневой узел tree бинарного дерева, показанного выше, она выведет

Как видно по порядку узлов в выводе, алгоритм сначала движется вниз по "левой ноге" дерева до самого низа, а затем по порядку проходит остальные узлы.

Аналогично можно написать алгоритм для вычисления суммы всех значений, хранящихся в узлах дерева:

def sum_of_nodes(root: Node):
    node_sum = root.value

    if root.left_child is not None:
        node_sum += sum_of_nodes(root.left_child)

    if root.right_child is not None:
        node_sum += sum_of_nodes(root.right_child)

    return node_sum

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

Отсортированное бинарное дерево

Бинарное дерево особенно полезно, когда узлы отсортированы определенным образом. Это делает поиск узлов в дереве быстрым и эффективным.

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

Теперь мы можем написать рекурсивный алгоритм поиска узлов. Идея очень похожа на бинарный поиск из предыдущего раздела: если текущий узел - тот, который мы ищем, вернуть True. Иначе продолжить рекурсивно либо с левым, либо с правым дочерним деревом. Если узел не определен, вернуть False.

def find_node(root: Node, value):
    if root is None:
        return False

    if value == root.value:
        return True

    if value > root.value:
        return find_node(root.right_child, value)

    return find_node(root.left_child, value)

Возвращаясь ко временам до рекурсии

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

Ответьте, пожалуйста, на короткую анкету по этой части курса.

Текущие баллы можно посмотреть в синем индикаторе в правом нижнем углу страницы.