Что такое рекурсия и как с ней работать: разбираемся на примерах
В статье рассказываем об основах рекурсии и разбираем эту функцию на примерах.
553 открытий1К показов

Рекурсия — это мощный инструмент в программировании, который позволяет решать задачи, разбивая их на более простые подзадачи. В статье рассмотрим базовые понятия рекурсии, её принципы, примеры использования, а также типичные проблемы, с которыми можно столкнуться при написании кода.
Рекурсия: что это такое и зачем нужна
Рекурсия — функция, которая вызывает саму себя. Ее базовое применение — разбить большую задачу на несколько мелких, что делает код проще и понятнее, или когда нужно повторить какое-то действие несколько раз. Второй случай похож на русскую матрешку — вы достаете куклу за куклой, пока не дойдете до самой маленькой.
А теперь давайте разберемся на простом примере из математики: представим, что у нас есть функция F, которая выполняет определенное действие. В нашем случае — вычисляет факториал числа (это самый классический пример). Внутри этой функции F в качестве одного из значений используем вызов этой же функции F, но с уменьшенным аргументом. Так функция будет вызывать саму себя до тех пор, пока не достигнет базового случая (о нем расскажем ниже), после чего начнет возвращать результаты.
В виде кода это выглядит так:
Здесь функция F вычисляет факториал числа n, умножая его на факториал n-1, и так до тех пор, пока не дойдёт до 1, после чего начнёт возвращать результаты вверх по цепочке вызовов. Этот пример как раз о том, что нужно выполнить несколько одинаковых действий.
А вот пример из жизни: вы листаете ленту в известной социальной сети, а новые посты обновляются автоматически — это рекурсия в действии.
Принципы работы рекурсии
Рекурсия строится на двух ключевых принципах: базовый случай и рекурсивный вызов. Они позволяют функции вызывать саму себя, пока она не завершится.
Базовый случай
Базовый случай рекурсии — условие, при котором рекурсивный вызов прекращается. Без него функция будет вызывать саму себя бесконечно, а значит, стек переполнится.
Один из самых простых примеров — факториал, о котором мы писали выше. Другой — возведение числа в степень до тех пор, пока значение не станет равно искомому.
Так это выглядит в виде кода:
То есть, базовый случай — если exponent == 0, то возвращаем 1.
Рекурсивный вызов
Рекурсивный вызов — шаг, на котором функция вызывает саму себя, но с измененными параметрами, чтобы задача стала проще. Один из еще одних классических примеров — задача с числами Фибоначчи.
Числа Фибоначчи — это последовательность, где каждое число равно сумме двух предыдущих: 0, 1, 1, 2, 3, 5, 8, 13, 21, …
Если вызвать fibonacci(5)
, то увидите следующее:
После этого функция возвращает результаты обратно вверх по стеку вызовов. Обычно этот метод используется в криптографии и алгосах.
Кстати, на примере чисел Фибоначчи можно разобрать одну из проблем рекурсии — плохая производительность при отсутствии мемоизации.
Мемоизация — техника оптимизации, при которой результаты больших вычислений сохраняются и используются еще раз при повторных вызовах функции. Это особенно полезно, если работаете с рекурсиями, которые могут вычислять одни и те же значения много раз.
Так, функция в задаче с числами Фибоначчи имеет экспоненциальную сложность O(2^n), так как она многократно вычисляет одни и те же значения. Например, чтобы вычислить fibonacci(5), функция вызывает сама себя 15 раз, хотя уникальных вычислений всего 6.
Чтобы улучшить производительность, нужно использовать мемоизацию, чтобы сохранить результаты:
Здесь сложность уменьшается до O(n), так как каждое значение вычисляется только один раз.
Стек вызовов и управление памятью
Каждый рекурсивный вызов функции добавляет новый элемент в стек вызовов. Это значит, что вызовы складывается в стеке до тех пор, пока не будет достигнут базовый случай. После этого стек начинает разворачиваться, возвращая результаты на каждом уровне.
Например:
Так, когда мы вызываем сountdows(3), в стеке появляются новые вызовы:
call countdown(3) # → печатает 3
call countdown(2) # → печатает 2
call countdown(1) # → печатает 1
call countdown(0) # → печатает "Старт" и выходит
Затем стек начинает разворачиваться:
- countdown(0) завершился → удаляется из стека
- countdown(1) завершился → удаляется из стека
- countdown(2) завершился → удаляется из стека
- countdown(3) завершился → удаляется из стека
Если же в рекурсии нет базового случая, то стек вызовов никогда не освободится, и программа (в нашем случае на Питоне) выдаст ошибку RecursionError.
Вот пример бесконечной рекурсии:
В Питоне есть ограничения до 1000 вызовов, чтобы не перегружать стек, но этот лимит можно увеличить:
Рекурсия на реальных задачах
С базовым случаем и рекурсивным вызовом все понятно, поэтому давайте разбираться на более реальных и сложных примерах — с деревьями, графами и массивами.
Обход структуры данных
Рекурсия часто используется для обхода деревьев и графов. Например, бинарного дерева — в нем не более двух дочерних узлов (левый и правый). Вот три основных способа обхода:
- Прямой обход (Pre-order): Корень → Левый узел → Правый узел.
- Симметричный обход (In-order): Левый узел → Корень → Правый узел.
- Обратный обход (Post-order): Левый узел → Правый узел → Корень.
Запишем в виде кода:
Дерево будет выглядеть так:
1
/ \
2 3
/ \
4 5
- Прямой обход: 1 → 2 → 4 → 5 → 3.
- Симметричный обход: 4 → 2 → 5 → 1 → 3.
- Обратный обход: 4 → 5 → 2 → 3 → 1.
Обходить можно и графы, особенно в глубине (DFS). Вот пример:
Сам граф:
Результат обхода: A → B → D → E → F → C.
Разбиение
Разбить можно массив или строку. Давайте разбираться на примере строки. Так, рекурсия может разбить строку на слова или разделить ее по конкретным символам. Выглядит это так:
Что такое хвостовая рекурсия
Хвостовая (оконечная) рекурсия — частный случай рекурсии. Главное отличие от обычной в том, что единственный рекурсивный вызов находится в конце перед выходом функции. В традиционной же рекурсии после рекурсивного вызова могут быть дополнительные вычисления.
Вот пример:
Кстати, с помощью хвостовой рекурсии тоже можно решать задачи с числами Фибоначчи:
Некоторые языки программирования (например, Haskell и Scala) поддерживают оптимизацию хвостовой рекурсии. Это означает, что компилятор или интерпретатор преобразует хвостовую рекурсию в итерацию — это помогает избежать переполнение стека.
Давайте посмотрим, как это работает в Scala. Вот обычная рекурсия, чтобы понять принцип:
А вот рекурсия с оптимизацией:
К сожалению, наш любимый Питон такую функцию не поддерживает, но всегда можно преобразовать «хвостика» в итерацию вручную:
Это пример итеративного решения факториала.
Рекурсия vs. итерация
Основные различия между рекурсией и итерацией заключаются в следующем:
- В рекурсии функция вызывает саму себя, а в итерации используются циклы.
- Интеграция требует меньше памяти, потому что нет стека вызовов.
- Рекурсия медленнее без оптимизации.
- С рекурсией легко переполнить хранилище при большой глубине.
- Рекурсия обычно более читаемая и лаконичная, но подходит для меньшего количества задач.
Итерацию лучше использовать в следующих случаях:
- Задачи, где нужна производительность. Как, например, с итеративным вычислением чисел Фибоначчи.
- Обработка больших данных, например, поиск или сортировка. Вот пример пузырьковой сортировки:
- Задачи с большой глубиной рекурсии, чтобы стек не переполнялся. Вот как итеративно обойти дерево:
Еще один пример: задача «Ханойские башни»
«Ханойские башни» — классная головоломка, которую часто решают с помощью рекурсии. Считайте, что это еще одна классика.
Есть три стержня: A, B и C. На стержень A нанизано несколько дисков разного размера, причем диски упорядочены по размеру в виде пирамидки — вниз от маленького к большому. Суть в том, чтобы переместить все диски со стержня А на С, при этом: за один раз можно перемещать только один диск, нельзя класть больший диск на меньший, можно использовать стержень B как вспомогательный.
Рекурсивное решение задачи «Ханойские башни» основано на следующей идее:
- Переместить (n−1) дисков с A на B, используя C как промежуточный.
- Переместить оставшийся самый большой диск с A на C.
- Переместить (n−1) дисков с B) на C, теперь используя A как промежуточный.
Следовательно, если количество дисков n=1, просто переместите его с А на С (базовый случай). В остальных случаях при n–1 повторить то, что указано выше.
А теперь решение с помощью кода:
Вывод:
Поздравляем, вы великолепны. А если хотите еще потренироваться в рекурсии, то можно написать код для поиска пути в лабиринте (кстати, это чем-то напоминает онлайн-карты и навигаторы) или обратного вывода строки.
553 открытий1К показов