Зарегистрируйтесь, чтобы продолжить обучение

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

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

Что такое рекурсия

Рекурсия в программировании — это вызов функции из этой же самой функции. В математике многие функции определены именно таким образом, поэтому и большинство языков программирования берет на вооружение этот подход. 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à!

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

  1. Простой базовый случай или терминальный сценарий. Это точка, в которой нужно остановиться. В нашем примере это 0: мы остановили вычисление факториала, когда в функцию был передан 0
  2. Правило передвижения по рекурсии, углубление. В нашем случае это было 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-элементов, и одни элементы могут входить в другие. Теги в тегах в тегах. И для эффективной обработки страницы браузеру требуется рекурсивно двигаться от уровня к уровню чтобы понять, в каком именно виде нужно вывести эти элементы на экран для пользователя.

Пример уже знакомой вам рекурсивной задачи - выпрямление списка. Для решения ее нужно извлечь элементы из каждого вложенного списка. А в свою очередь и из каждого вложенного во вложенный и так далее. Получается рекурсия.

def flatten(nested_list):
    flat_list = []

    for item in nested_list:
        # Если элемент - список, рекурсивно обрабатываем его
        if isinstance(item, list):
            flat_list.extend(flatten(item))
        else:
            flat_list.append(item)

    return flat_list

nested = [1, [2, [3, 4], 5], [6, 7]]
print(flatten(nested)) # => [1, 2, 3, 4, 5, 6, 7]

Вы будете постоянно сталкиваться с рекурсией в этом и последующих курсах, потому что это невероятно мощная штука.

Выводы

В этом уроке мы узнали, что такое рекурсия — это возможность дать определение функции, используя в процессе саму определяемую функцию.


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

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

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

Для полного доступа к курсу нужен базовый план

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

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

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

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

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

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

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff