Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

Рекурсия Python: Функции

"Чтобы понять рекурсию, нужно сначала понять рекурсию!" (расхожая шутка).

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

def factorial(n):
    if n <= 0:
        return 1
    return n * factorial(n - 1)

Эта функция, вычисляет факториал числа 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)

Здесь в теле функции рекурсивных вызова два, но в каждом конкретном "заходе" используется только один.

А вот рекурсия в этой функции (которая вычисляет очередное Число Фибоначчи) — каскадная:

def fibonacci(n):
    if n <= 2:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

Здесь функция всегда вызывает себя два раза. Сначала будет два вызова себя, которые превратятся в четыре (два раза по два вызова), затем в восемь — количество вызовов растёт "каскадно", отсюда и название рекурсии.

Заключение

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


Аватары экспертов Хекслета

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты.

Ошибки, сложный материал, вопросы >
Нашли опечатку или неточность?

Выделите текст, нажмите ctrl + enter и отправьте его нам. В течение нескольких дней мы исправим ошибку или улучшим формулировку.

Что-то не получается или материал кажется сложным?

Загляните в раздел «Обсуждение»:

  • задайте вопрос. Вы быстрее справитесь с трудностями и прокачаете навык постановки правильных вопросов, что пригодится и в учёбе, и в работе программистом;
  • расскажите о своих впечатлениях. Если курс слишком сложный, подробный отзыв поможет нам сделать его лучше;
  • изучите вопросы других учеников и ответы на них. Это база знаний, которой можно и нужно пользоваться.
Об обучении на Хекслете

Для полного доступа к курсу нужна профессиональная подписка

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

Получить доступ
900
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.

  • 120 курсов, 2000+ часов теории
  • 900 практических заданий в браузере
  • 360 000 студентов
Отправляя форму, вы соглашаетесь c «Политикой конфиденциальности» и «Условиями оказания услуг»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff
Рекомендуемые программы

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

Иконка программы Python-разработчик
Профессия
Разработка веб-приложений на Django
29 сентября 8 месяцев

Есть вопрос или хотите участвовать в обсуждении?

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы соглашаетесь c «Политикой конфиденциальности» и «Условиями оказания услуг»