В этом уроке мы узнаем, что такое рекурсия, зачем она нужна и чем отличается рекурсия в математике и в языках программирования. Еще мы разберем условие завершения рекурсии и обсудим, какие виды рекурсии существуют.
Что такое рекурсия
Рекурсия в программировании — это вызов функции из этой же самой функции. В математике многие функции определены именно таким образом, поэтому и большинство языков программирования берет на вооружение этот подход. Python здесь не является исключением: в определении функции вы можете использовать не только данные, определенные ранее, но и вызывать в теле функции саму определяемую функцию. Выглядит это так:
def f():
f()
Этот вызов будет выполняться бесконечно и кажется, что в этом нет никакого смысла. Попробуем осмыслить рекурсию на более повседневном примере. Допустим, у вас есть три книги на полке и вы хотите узнать, сколько есть возможных вариантов их перестановки.
Получается шесть уникальных комбинаций из трех книг. Из четырех — 24 комбинации. Из 13 — почти столько же, сколько людей на планете. 25 книг? Вариантов их перестановки больше, чем атомов в организме человека.
Вообще, существует n! вариантов перестановки n книг. Факториал означает — перемножить все целые числа от 1 до n. Так что, 3! это 1 * 2 * 3. Давайте напишем функцию факториала.
def factorial(n):
return 1 * 2 * 3 * 4
Здесь что-то не так. Мы не знаем значение n изначально, в этом вся проблема. Из математики нам известны два условия для рекурсивного определения факториала: если n равно 0, тогда факториал — 1, это просто. Но если n не равно 0, тогда факториал — n*(n-1)!.
Давайте попробуем вот так:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
answer = factorial(3)
Это может показаться странным. Мы вызываем функцию из функции, но… это та же самая функция! Все дело в том, что сама по себе функция — это не ящик, это его описание. Ящик создается лишь при вызове функции, а после того, как она выполнилась, ящик самоуничтожается. Поэтому когда вы вызываете ту же самую функцию из нее самой, просто создается еще один ящик.
Давайте это отследим: мы вызываем factorial(3). 3 это не 0, поэтому первое условие игнорируется. Функция хочет произвести умножение чисел и вернуть ответ, но она не может — ей нужно знать второе число, для чего она вызывает factorial(3 - 1) или factorial(2).
Формируется новый идентичный ящик factorial, он принимает число 2, это не 0, так что он пробует произвести умножение и вернуть ответ. Но не может — ему нужно знать второе число, поэтому он вызывает factorial(1).
Формируется новый идентичный ящик factorial, он принимает число 1 и это снова не 0. Еще одна попытка произвести умножение и вернуть результат, происходит вызов factorial(0) и этот ящик уже может мгновенно вернуть ответ — он возвращает 1.
1 возвращается в предыдущий ящик, умножается на 1 и ответ "1" возвращается в предыдущий ящик, умножается на 2 и ответ "2" возвращается в предыдущий ящик, умножается на 3 и ответ "6" возвращается во внешний мир и сохраняется в константе answer. Voilà!
Все это и есть рекурсия: что-то описывается через самого себя, содержит себя в своем описании. Когда дело касается математики или программирования, требуется два условия:
- Простой базовый случай или терминальный сценарий. Это точка, в которой нужно остановиться. В нашем примере это 0: мы остановили вычисление факториала, когда в функцию был передан 0
- Правило передвижения по рекурсии, углубление. В нашем случае это было
n * factorial(n - 1)
Еще один момент. Если проверить наш код с помощью линтера, то он выдаст ошибку no-else-return. Последуем рекомендациями линтера и отрефакторим код:
def factorial(n):
if n == 0
return 1
return n * factorial(n - 1)
answer = factorial(3)
Давайте проследим шаги еще раз, но с другой точки зрения, не заглядывая в ящики. Вот, как это выглядит пошагово:
factorial(3)
3 * factorial(2)
3 * 2 * factorial(1)
3 * 2 * 1 * factorial(0)
3 * 2 * 1 * 1
3 * 2 * 1
3 * 2
6
Умножение не происходит пока мы спускаемся до базового случая функции factorial(0). А затем мы возвращаемся наверх, производя одно умножение за один шаг.
Рекурсия широко используется, особенно в функциональном программировании, как уже упоминалось ранее. И не только для математических вычислений, а для множества других процессов!
Зачем нужна рекурсия
Некоторые алгоритмы реализуются проще, если использовать именно рекурсию, а не циклы. Часто такие алгоритмы работают с рекурсивными структурами данных — деревьями, «словарями словарей словарей» и подобными. Например, веб-страницы состоят из HTML-элементов, и одни элементы могут входить в другие. Теги в тегах в тегах. И для эффективной обработки страницы браузеру требуется рекурсивно двигаться от уровня к уровню, чтобы понять, в каком именно виде нужно вывести эти элементы на экран для пользователя. При реализации таких алгоритмов нужно помнить, что память для стека конечна. При этом обычно конечны и сами обрабатываемые структуры данных, поэтому отказываться полностью от рекурсии не стоит.
Виды рекурсии
Рекурсии можно разделить на два вида по тому, как они себя вызывают:
- Прямая — когда функция вызывает себя
- Косвенная — когда одна функция внутри себя вызывает другую функцию, которая когда-то вызовет первую
Так же рекурсии можно разделить по количеству рекурсивных вызовов:
- Линейная — когда при вычислении результата функции функция вызывает себя один раз, как в примере с
factorial. Уточним, что «один раз» — это не про общее количество вызовов функции в теле. Речь идет о количестве вызовов, результаты которых нужны для одного общего вычисления - Каскадная — когда функция вызывает себя несколько раз
Рассмотрим подробнее линейную и каскадную рекурсию.
Пример линейной рекурсии
Если рекурсия в функции проверяет Гипотезу Коллатца, она считается линейной:
def collatz(n):
if n == 1:
return True
if n % 2 == 0:
return collatz(n // 2)
return collatz(n * 3 + 1)
Интерактивный пример: https://replit.com/@hexlet/python-functions-recursion-collatz#main.py
Здесь в теле функции есть два рекурсивных вызова, но в каждом заходе используется только один.
Еще один пример использования линейной рекурсии — обход коллекций. Для этого можно рекурсивно представить коллекцию как:
- Начало (голову)
- Остальную часть коллекции (хвост)
Дальше хвост также можно разложить на голову и новый хвост. И так до тех пор, пока не останется голова и пустой хвост:
[1, 2, 3] ->
[1, [2, 3]] ->
[1, [2, [3]]] ->
[1, [2, [3, []]]]
При рекурсивной обработке коллекции мы будем обходить коллекцию и дробить старый хвост на новую голову и новый хвост на каждой итерации. Так мы делаем до тех пор, пока не получим пустой хвост — то есть конец коллекции:
# Функция рекурсивно обходит список, суммируя числа из него
def sum(array):
# Мы можем использовать оператор упаковки для записи в хвост остальной части списка
head, *tail = array
if not tail:
return head
return head + sum(tail)
Пример каскадной рекурсии
Если рекурсия в функции вычисляет очередное Число Фибоначчи, она называется каскадной:
def fibonacci(n):
if n <= 2:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
Интерактивный пример: https://replit.com/@hexlet/python-functions-recursion-fibonacci#main.py
Здесь функция всегда вызывает себя два раза. Сначала будет два вызова, которые превратятся в четыре — два раза по два вызова. Затем в восемь — количество вызовов растет каскадно.
Выводы
В этом уроке мы узнали, что такое рекурсия — это возможность дать определение функции, используя в процессе саму определяемую функцию. Также мы познакомились с видами рекурсии. Она бывает прямой, косвенной, линейной и каскадной. Последние две мы подробнее разобрали на примерах.
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
- Статья «Как учиться и справляться с негативными мыслями»
- Статья «Ловушки обучения»
- Статья «Сложные простые задачи по программированию»
- Вебинар «Как самостоятельно учиться»
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
