Рекурсия

До сих пор функция у вас всегда вызывала что-то другое: print(), другую вашу функцию, встроенный метод. А что, если функции понадобится вызвать саму себя? Звучит как парадокс, но это законный приём, и без него неудобно решать задачи, которые сами устроены "матрёшкой": разложить число на множители через более простое число, посчитать сумму вложенных списков, обойти папку с папками внутри папок. Разберём, как это работает и где эта техника подводит новичков.

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

Представьте матрёшку. Открываете большую куклу — внутри такая же, только чуть меньше. Открываете её — снова такая же, ещё меньше. И так, пока не дойдёте до самой маленькой, которая уже не открывается: это дно, дальше открывать нечего. Без такого "дна" матрёшки открывались бы бесконечно, а такого не бывает.

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

У любой рабочей рекурсии обязательно есть два компонента:

• Базовый случай — самая простая ситуация, где ответ известен сразу, без нового вызова себя. Это та самая нераскрывающаяся кукла.
• Рекурсивный случай — ситуация, где функция вызывает себя с более простым, уменьшенным аргументом, приближаясь к базовому случаю на каждом шаге.

Если базового случая нет или до него нельзя дойти, функция будет вызывать себя бесконечно — про это будет отдельный раздел ниже.

Первый пример: факториал

Возьмём задачу, где рекурсивность видна прямо в определении. Факториал числа n (записывается n!) — это произведение всех целых чисел от 1 до n. Например, 5! = 5 × 4 × 3 × 2 × 1 = 120.

Присмотритесь: 5! — это 5, умноженное на 4!. А 4! — это 4, умноженное на 3!. Получается, что факториал числа n можно выразить через факториал числа n - 1: n! = n × (n - 1)!. Это и есть рекурсивное определение, только базовый случай нужно задать отдельно: факториал 0 и факториал 1 равны 1 — дальше раскладывать нечего.

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

print(factorial(5))

Разберём построчно:

• def factorial(n): — объявляем функцию с одним параметром n: числом, для которого считаем факториал.
• if n <= 1: — проверка базового случая. Если n равно 0 или 1, дальше раскладывать нечего.
• return 1 — при базовом случае функция сразу отвечает числом 1 и не вызывает себя ещё раз.
• return n * factorial(n - 1) — рекурсивный случай: если n больше 1, функция умножает n на результат вызова самой себя, но уже с аргументом на единицу меньше. Именно так n постепенно приближается к базовому случаю.
• print(factorial(5)) — вызываем функцию с числом 5 и печатаем результат. Выведется 120.

Чтобы понять, откуда взялось 120, полезно проследить, как разворачиваются вызовы. Сначала идёт погружение: factorial(5) вызывает factorial(4) и ждёт ответа, та вызывает factorial(3), дальше factorial(2), и наконец factorial(1) — это базовый случай, он сразу отвечает 1, никого больше не вызывая. Затем начинается всплытие: каждый вызов получает ответ от следующего и умножает на него своё n:

• factorial(1) вернул 1
• factorial(2) посчитал 2 * 1 = 2 и вернул его
• factorial(3) посчитал 3 * 2 = 6 и вернул его
• factorial(4) посчитал 4 * 6 = 24 и вернул его
• factorial(5) посчитал 5 * 24 = 120 — это и есть окончательный ответ

Числа Фибоначчи: когда рекурсия начинает тормозить

Ряд Фибоначчи выглядит так: 0, 1, 1, 2, 3, 5, 8, 13, 21 и так далее — каждое следующее число равно сумме двух предыдущих. Определение снова рекурсивное само по себе: n-е число Фибоначчи — это сумма (n - 1)-го и (n - 2)-го чисел, а базовых случаев здесь два, потому что рекурсивному вызову нужно "оттолкнуться" сразу от двух предыдущих чисел, а не от одного.

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

print(fib(10))

• if n <= 1: return n — базовый случай сразу для двух чисел: fib(0) возвращает 0, fib(1) возвращает 1.
• return fib(n - 1) + fib(n - 2) — рекурсивный случай: функция вызывает себя дважды, для n - 1 и для n - 2, и складывает результаты.
• print(fib(10)) — выведет 55: это десятое число в ряду, если считать с нуля.

Код выглядит невинно, но попробуйте посчитать fib(35) — программа задумается на несколько секунд. Причина в том, что каждый вызов с двумя рекурсивными вызовами внутри порождает ещё два, а те — ещё по два: при вычислении fib(5) значение fib(3) посчитается дважды, fib(2) — трижды, и с ростом n число повторных, совершенно одинаковых вычислений растёт очень быстро.

RecursionError: что будет, если забыть базовый случай

Помните образ двух зеркал, поставленных друг напротив друга? Вы видите отражение внутри отражения внутри отражения — и без стены, которая это остановит, будет продолжаться бесконечно. Именно это происходит, если в рекурсивной функции забыть про базовый случай или написать условие так, что до него невозможно дойти.

def endless(n):
    return endless(n + 1)

endless(1)

• def endless(n): — функция принимает число n.
• return endless(n + 1) — на каждом шаге функция вызывает саму себя с n, увеличенным на 1. Условия остановки нет вообще — базовый случай отсутствует.
• endless(1) — вызов запускает цепочку, которая никогда не дойдёт до ответа сама по себе.

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

RecursionError: maximum recursion depth exceeded

RecursionError почти всегда означает одно из двух: либо в функции нет базового случая, либо он есть, но аргумент к нему не приближается (как выше, где n только растёт). Увидев эту ошибку, ищите: доходит ли аргумент до значения, при котором сработает if с базовым случаем.

Как ускорить Фибоначчи: запоминаем то, что уже посчитали

Представьте, что вы решаете одну и ту же арифметическую задачку на экзамене несколько раз подряд, потому что забываете, какой ответ у вас уже получился. Именно так вела себя наивная рекурсия Фибоначчи: она честно пересчитывала одни и те же значения заново, вместо того чтобы один раз посчитать и записать ответ на черновик.

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

cache = {}

def fib_memo(n):
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    result = fib_memo(n - 1) + fib_memo(n - 2)
    cache[n] = result
    return result

print(fib_memo(50))

• cache = {} — пустой словарь снаружи функции: живёт, пока идут все вызовы, и хранит пары "n — уже посчитанный ответ".
• if n in cache: return cache[n] — если fib(n) уже считали, сразу отдаём готовый ответ из словаря, без новых вызовов.
• if n <= 1: return n — обычный базовый случай, как и раньше.
• result = fib_memo(n - 1) + fib_memo(n - 2) — если ответа в кэше нет, считаем его как обычно, двумя рекурсивными вызовами, и cache[n] = result запоминает результат перед возвратом.
• print(fib_memo(50)) — без запоминания результатов посчитать fib(50) наивной рекурсией практически нереально, а с кэшем ответ приходит мгновенно.

Зачем это в жизни: обход вложенных структур

По-настоящему рекурсия раскрывается там, где данные сами вложены друг в друга: список внутри списка, папка внутри папки. Обычный for легко переберёт плоский список, но если внутри встретится ещё один список, а в нём ещё один — заранее не известно, на сколько уровней вглубь придётся заглянуть. Рекурсия решает это естественно: функция сама вызывает себя на каждый вложенный список, независимо от глубины.

Чтобы отличить внутри цикла обычное число от вложенного списка, понадобится ещё одна готовая функция — isinstance(значение, тип). Она проверяет, относится ли значение к указанному типу, и возвращает True или False. Например, isinstance(5, list) вернёт False (5 — не список), а isinstance([1, 2], list) вернёт True.

def nested_sum(items):
    total = 0
    for item in items:
        if isinstance(item, list):
            total += nested_sum(item)
        else:
            total += item
    return total

print(nested_sum([1, 2, [3, 4], 5]))

• def nested_sum(items): — функция принимает список, в котором могут встречаться и числа, и вложенные списки.
• total = 0 и for item in items: — как обычно, накапливаем сумму и перебираем элементы по одному.
• if isinstance(item, list): total += nested_sum(item) — если элемент сам оказался списком, вызываем ту же функцию для него и прибавляем то, что она вернёт. Базовый случай здесь не отдельная строка с if, а сама структура данных: рано или поздно список закончится, и for просто ни разу не выполнится — функция вернёт 0.
• else: total += item — если элемент не список, значит это число, и оно просто прибавляется к сумме.
• return total — возвращаем сумму текущего уровня. print(nested_sum([1, 2, [3, 4], 5])) выведет 15: 1 + 2 + (3 + 4) + 5.

Рекурсия или цикл: что выбрать

Любую рекурсию можно переписать через цикл, и наоборот — вопрос не в том, что "правильнее", а в том, что читается яснее для конкретной задачи.

Простое правило: "матрёшечная" задача — берите рекурсию, линейная — берите цикл.

Частые ошибки