- Что такое рекурсия
- Условие завершения рекурсии
- Переполнение стека
- Зачем нужна рекурсия
- Виды рекурсии
- Выводы
В этом уроке мы узнаем, что такое рекурсия, зачем она нужна и чем отличается рекурсия в математике и в языках программирования. Еще мы разберем условие завершения рекурсии и обсудим, какие виды рекурсии существуют.
Что такое рекурсия
Рекурсия в программировании — это возможность дать определение функции, используя в процессе саму определяемую функцию. В математике многие функции определены именно таким образом, поэтому и большинство языков программирования используют этот подход.
Это работает и в Python. Обычно в определении функции можно использовать только определения, которые дали ранее. Но есть одно исключение — функция в своем теле может вызывать себя. Выглядит это так:
def factorial(n):
if n <= 0:
return 1
return n * factorial(n - 1)
Интерактивный пример: https://replit.com/@hexlet/python-functions-recursion-factorial#main.py
Эта функция вычисляет факториал числа n
через умножение числа на факториал числа n - 1
.
Условие завершения рекурсии
В примере выше используется условие, которое прекращает рекурсию. Если в этой функции убрать условие, которое проверяет аргумент на неотрицательность, то первый же вызов этой функции заставит программу зациклиться — функция продолжит вызывать себя постоянно.
В определениях рекурсивных функций практически всегда есть подобное условие. Оно позволяет вычислению пойти по одной из веток:
- По рекурсивной — в этой ветке произойдет вызов себя
- По терминальной — закончит вычисление и вернет результат
Какой-то из аргументов рекурсивной функции должен обязательно убывать. В качестве убывания может быть:
- Уменьшение счетчика
- Отбрасывание головы списка при движении к его хвосту
- Вызов себя для части исходной структуры при обработке древовидных структур данных
Чтобы понять, что программа не зациклится, используют метод «пристального взгляда» и тесты. Особенно важно проверять срабатывание условия завершения рекурсии.
Переполнение стека
В большинстве программ, написанных на поддерживающих вызов функции языках, этот вызов устроен так: перед вызовом функции текущее место в программе запоминается в стеке. А когда функция возвращает результат, то соответствующий элемент стека отбрасывается.
Стек (stack) — это абстрактный тип данных, который похож на стопку монет. Монета, которую положили последней, будет снята первой. И при снятии монет порядок получается обратным порядку складывания.
В этом же стеке сохраняются значения аргументов функции, а иногда и другая служебная информация. При этом память, которая выделяется для стека при запуске программы, конечна и ограничена.
Если функция будет вызывать себя постоянно и не возвращать результат, то память в итоге закончится. Когда заканчивается память, выделенная для стека вызовов, стек переполняется.
В итоге мы не сможем посчитать факториал для достаточно больших чисел с помощью рекурсивной функции. Но сможем посчитать с помощью итеративной — написанной с использованием циклов и переменных.
Так выглядит переполнение стека при подсчете факториала:
factorial(1000)
# Traceback (most recent call last):
# File "<stdin>", line 1, in <module>
# File "<stdin>", line 4, in factorial
# File "<stdin>", line 4, in factorial
# File "<stdin>", line 4, in factorial
# [Previous line repeated 995 more times]
# File "<stdin>", line 2, in factorial
# RecursionError: maximum recursion depth exceeded in comparison
Сообщение говорит, что превышена максимальная глубина рекурсии. Глубиной рекурсии называется количество последовательных вызовов себя без возврата значения. В Python максимальная длина искусственно ограничена, потому что проще считать количество вызовов, чем предсказывать окончание памяти.
Зачем нужна рекурсия
Некоторые алгоритмы реализуются проще, если использовать именно рекурсию, а не циклы. Часто такие алгоритмы работают с рекурсивными структурами данных — деревьями, «словарями словарей словарей» и подобными. При реализации таких алгоритмов нужно помнить, что память для стека конечна. При этом обычно конечны и сами обрабатываемые структуры данных, поэтому отказываться полностью от рекурсии не стоит.
Виды рекурсии
Рекурсии можно разделить на два вида по тому, как они себя вызывают:
- Прямая — когда функция вызывает себя
- Косвенная — когда одна функция внутри себя вызывает другую функцию, которая когда-то вызовет первую
Так же рекурсии можно разделить по количеству рекурсивных вызовов:
- Линейная — когда при вычислении результата функции функция вызывает себя один раз, как в примере с
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
Здесь функция всегда вызывает себя два раза. Сначала будет два вызова, которые превратятся в четыре — два раза по два вызова. Затем в восемь — количество вызовов растет каскадно.
Выводы
В этом уроке мы узнали, что такое рекурсия — это возможность дать определение функции, используя в процессе саму определяемую функцию. Также мы познакомились с видами рекурсии. Она бывает прямой, косвенной, линейной и каскадной. Последние две мы подробнее разобрали на примерах.
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
- Статья «Как учиться и справляться с негативными мыслями»
- Статья «Ловушки обучения»
- Статья «Сложные простые задачи по программированию»
- Вебинар «Как самостоятельно учиться»
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.