Рекурсивное мышление в Python

Содержание

«Из всех идей, которые я предлагал детям, рекурсия выделяется как единственная идея, которая особенно способна вызвать восторженный отклик».

— Сеймур Паперт, Mindstorms

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

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

Дорогой питонический Дед Мороз…   ↑

Понимаю, что как коллеги-питонисты, мы все здесь по-факту взрослые, но, кажется, дети лучше понимают красоту рекурсии. Так что на мгновение перестанем быть взрослыми и поговорим о том, как мы можем использовать рекурсию, чтобы помочь Деду Морозу.

Вы когда-нибудь задумывались, как он раздаёт новогодние подарки? Я уверен и считаю, что у Деда Мороза со Снегурочками есть список адресов, куда они должны зайти. Они идут в дом, раздают подарки, едят печенье с молоком и переходят к следующему в списке дому. Поскольку этот алгоритм раздачи подарков основан на явном построении цикла, он называется итерационным алгоритмом.

Алгоритм итеративной раздачи подарков, реализованный на Python:

houses = ["Васькин дом", "Петин дом", "Марусин дом", "Иванов дом"]

def deliver_presents_iteratively():
    for house in houses:
        print("Подарки в", house)

>>> deliver_presents_iteratively()
Подарки в Васькин дом
Подарки в Петин дом
Подарки в Марусин дом
Подарки в Иванов дом

Но я сочувствую Деду Морозу. В его то возрасте не нужно разносить все подарки самому. Я предлагаю алгоритм, с помощью которого он может разделить работу по доставке подарков между своими Снегурочками:

1. Назначьте Снегурочку и отдайте ей всю работу
2. Назначайте Снегурочкам статусы и обязанности в зависимости от количества домов, за которые они несут ответственность:
   • > 1 — старшая Снегурочка и может разделить работу между двумя своими сестрёнками.
   • = 1 — младшенькая сестрёнка и должна сама доставить и раздать подарки в назначенный ей дом

Это типичная структура рекурсивного алгоритма. Если текущая проблема представляет собой простой случай, решите ее. Если нет, разделите его на подзадачи и примените к ним ту же стратегию.

Алгоритм рекурсивной доставки и раздачи подарков, реализованный на Python:

houses = ["Васькин дом", "Петин дом", "Марусин дом", "Иванов дом"]

# Каждый вызов функции представляет Снегурочку, выполняющую свою работу 
def deliver_presents_recursively(houses):
    # Снегурочка делает свою работу
    if len(houses) == 1:
        house = houses[0]
        print("Подарки в", house)

    # Старшая Снегурочка делает свою работу
    else:
        mid = len(houses) // 2
        first_half = houses[:mid]
        second_half = houses[mid:]

        # Делит свою работу между двумя Снегурочками
        deliver_presents_recursively(first_half)
        deliver_presents_recursively(second_half)

 

>>> deliver_presents_recursively(houses)
Подарки в Васькин дом
Подарки в Петин дом
Подарки в Марусин дом
Подарки в Иванов дом

Рекурсивные функции в Python   ↑

Теперь, когда у нас есть некоторое представление о рекурсии, давайте введем формальное определение рекурсивной функции. Рекурсивная функция — это функция, определенная в терминах самой себя с помощью самореференциальных выражений.

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

Чтобы продемонстрировать эту структуру, давайте напишем рекурсивную функцию для вычисления n!:
Разложите исходную проблему на более простые экземпляры той же проблемы. Это рекурсивный случай:

n! = n \times (n-1) \times (n-2) \times (n-3) \times \dots \times 3 \times 2 \times 1
n! = n \times (n-1)!

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

n! = n \times (n-1)!
n! = n \times (n-1) \times (n-2)!
n! = n \times (n-1) \times (n-2) \times (n-3)!
.
.
.
n! = n \times (n-1) \times (n-2) \times (n-3) \dots \times 3!
n! = n \times (n-1) \times (n-2) \times (n-3) \dots \times 3 \times 2!
n! = n \times (n-1) \times (n-2) \times (n-3) \dots \times 3 \times 2 \times 1!

Вот, 1! это наш базовый случай, и он равен 1.

Рекурсивная функция для вычисления n! реализовано на Python:

def factorial_recursive(n):
    # Base case: 1! = 1
    if n == 1:
        return 1

    # Recursive case: n! = n * (n-1)!
    else:
        return n * factorial_recursive(n-1)

>>> factorial_recursive(5)
120

За кулисами каждый рекурсивный вызов добавляет кадр стека (содержащий контекст его выполнения) в стек вызовов, пока мы не дойдем до базового случая. Затем стек начинает раскручиваться, поскольку каждый вызов возвращает свои результаты:

Поддержание состояния   ↑

При работе с рекурсивными функциями имейте в виду, что каждый рекурсивный вызов имеет свой собственный контекст выполнения, поэтому для поддержания состояния во время рекурсии вам необходимо:

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

Следующий пример должен прояснить ситуацию. Давайте вычислим 1 + 2 + 3 + 10 с помощью рекурсии. Состояние, которое мы должны поддерживать (текущее число, которое мы добавляем, накопленная до сих пор сумма).

Вот как мы это сделаем, изменяя его при каждом рекурсивном вызове (т.е. передавая обновленное текущее состояние каждому рекурсивному вызову в качестве аргументов):

def sum_recursive(current_number, accumulated_sum):
    # Базовый вариант
    # Вернуть конечное состояние
    if current_number == 11:
        return accumulated_sum

    # Рекурсивный случай
    # Пропустите состояние через рекурсивный вызов
    else:
        return sum_recursive(current_number + 1, accumulated_sum + current_number)

# Передаем начальное состояние
>>> sum_recursive(1, 0)
55

Вот как мы поддержим состояние, сохраняя его в глобальном области видимости:

# Глобальное изменяемое состояние
current_number = 1
accumulated_sum = 0

def sum_recursive():
    global current_number
    global accumulated_sum
    # Базовый вариант
    if current_number == 11:
        return accumulated_sum
    # Рекурсивный случай
    else:
        accumulated_sum = accumulated_sum + current_number
        current_number = current_number + 1
        return sum_recursive()

>>> sum_recursive()
55

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

Рекурсивные структуры данных в Python   ↑

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

# Возвращаем новый список, который является результатом
# добавляем элемент в начало (т.е. перед) input_list
def attach_head(element, input_list):
    return [element] + input_list

Используя пустой список и операцию attach_head, вы можете создать любой список. Например, давайте сгенерируем [1, 46, -31, "hello"]:

attach_head(1,                                                  # вернёт [1, 46, -31, "hello"]
            attach_head(46,                                     # вернёт [46, -31, "hello"]
                        attach_head(-31,                        # вернёт [-31, "hello"]
                                    attach_head("hello", [])))) # вернёт ["hello"]

[1, 46, -31, 'hello']

1. Начиная с пустого списка, вы можете сгенерировать любой список, рекурсивно применяя функцию attach_head, и, таким образом, структура данных списка может быть определена рекурсивно как:

          +---- attach_head(element, smaller list)
   list = +
          +---- empty list
   

2. Рекурсию также можно рассматривать как композицию самореференциальной функции. Мы применяем функцию к аргументу, затем передаем результат в качестве аргумента второму приложению той же функции и так далее. Многократное создание attach_head с самим собой аналогично многократному вызову attach_head самого себя.

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

def list_sum_recursive(input_list):
    # Базовый вариант
    if input_list == []:
        return 0

    # Рекурсивный случай
    # Разложите исходную проблему на более простые экземпляры той же проблемы
    # используя тот факт, что ввод - это рекурсивная структура данных
    # и может быть определен как уменьшенная версия самого себя
    else:
        head = input_list[0]
        smaller_list = input_list[1:]
        return head + list_sum_recursive(smaller_list)

>>> list_sum_recursive([1, 2, 3])
6

Наивная рекурсия наивна   ↑

Числа Фибоначчи были первоначально определены итальянским математиком Фибоначчи в тринадцатом веке для моделирования роста популяций кроликов. Фибоначчи предположил, что количество пар кроликов, родившихся в данном году, равно количеству пар кроликов, родившихся от одной пары кроликов в двух предыдущих.

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

F_n = F_{n-1} + F_{n-2}

Базовые случаи:

F_0 и F_1

Напишем рекурсивную функцию для вычисления n-го числа Фибоначчи:

def fibonacci_recursive(n):
    print("Вычислено F", "(", n, ")", sep="", end=", ")

    # Базовый вариант
    if n == 0:
        return 0
    elif n == 1:
        return 1

    # Рекурсивный случай
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

>>> fibonacci_recursive(5)
Вычислено F(5), Вычислено F(4), Вычислено F(3), Вычислено F(2), Вычислено F(1), 
Вычислено F(0), Вычислено F(1), Вычислено F(2), Вычислено F(1), Вычислено F(0), 
Вычислено F(3), Вычислено F(2), Вычислено F(1), Вычислено F(0), Вычислено F(1),

5

Наивное следование рекурсивному определению n-го числа Фибоначчи было довольно неэффективным. Как видно из выходных данных выше, мы без необходимости пересчитываем значения. Давайте попробуем улучшить fibonacci_recursive, кэшируя результаты каждого вычисления Фибоначчи F_k:

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_recursive(n):
    print("Вычислено F", "(", n, ")", sep="", end=", ")

    # Базовый вариант
    if n == 0:
        return 0
    elif n == 1:
        return 1

    # Рекурсивный случай
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

>>> fibonacci_recursive(5)
Вычислено F(5), Вычислено F(4), Вычислено F(3), Вычислено F(2), Вычислено F(1), Вычислено F(0),

5

lru_cache — декоратор, который кеширует результаты. Таким образом, мы избегаем повторного вычисления, явно проверяя значение перед попыткой его вычисления. О lru_cache следует помнить одну вещь: поскольку он использует словарь для кеширования результатов, позиционные аргументы и аргументы ключевого слова (которые служат ключами в этом словаре) функции должны быть хешируемыми.

Непонятные подробности   ↑

Python не поддерживает исключение Хвостовая рекурсия^એ. В результате вы можете вызвать переполнение стека, если в конечном итоге вы используете больше кадров стека, чем глубина стека вызовов по умолчанию:

>>> import sys
>>> sys.getrecursionlimit()
3000

Помните об этом ограничении, если у вас есть программа, требующая глубокой рекурсии.

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

>>> input_list = [1, 2, 3]
>>> head = input_list[0]
>>> tail = input_list[1:]
>>> print("head --", head)
head -- 1
>>> print("tail --", tail)
tail -- [2, 3]

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

Fin   ↑

Однажды, меня спросили что такое рекурсия?. Я взял лист бумаги и написал: «Пожалуйста, переверните с обеих сторон». Вопрошающий не понял шутки, но теперь, когда вы прочитали эту статью, надеюсь, вы поняли ☺. Удачного питонинга!

На основе Thinking Recursively in Python