Рекурсия

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

Простой пример

Сумма чисел от 1 до n равна n плюс сумма от 1 до n - 1. А сумма от 1 до 0 — это просто 0. Так и запишем:

def total(n):
    if n == 0:          # база: ответ известен сразу
        return 0
    return n + total(n - 1)   # шаг: сводим к задаче поменьше

print(total(5))   # 15

У любой рекурсивной функции две части:

1. База — случай, когда ответ известен без новых вызовов. Без неё рекурсия не остановится.
2. Шаг — сведение задачи к той же задаче, но меньшей, так, чтобы рано или поздно прийти к базе.

Как это выполняется

Каждый вызов ждёт, пока вернётся вложенный:

total(3) = 3 + total(2)
               total(2) = 2 + total(1)
                              total(1) = 1 + total(0)
                                             total(0) = 0
                              total(1) = 1
               total(2) = 3
total(3) = 6

Вызовы складываются «стопкой», а потом разворачиваются обратно. Это видно, если печатать до и после вложенного вызова:

def countdown(n):
    if n == 0:
        print("Старт!")
        return
    print(n)
    countdown(n - 1)

countdown(3)    # 3, 2, 1, Старт!

Глубина рекурсии

Python ограничивает глубину — примерно 1000 вложенных вызовов. Дальше будет RecursionError. Для глубокой рекурсии лимит можно поднять:

import sys
sys.setrecursionlimit(10000)

Но если рекурсия — это просто цикл «от n до 0» на миллион шагов, лучше написать цикл.

Деление пополам

Рекурсия особенно хороша, когда задача делится на половины. Тогда глубина маленькая: для n = 10^18 — всего около 60 уровней.

Пример: сколько раз можно делить число пополам (нацело), пока оно не станет единицей?

def halvings(n):
    if n == 1:
        return 0
    return 1 + halvings(n // 2)

print(halvings(1000))   # 9

Такая идея — «решить для половины и достроить ответ» — встречается во многих быстрых алгоритмах.

Числа Фибоначчи и повторные вычисления

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

Код верный, но для n = 40 работает очень долго: fib(38) считается дважды, fib(37) — трижды и так далее. Число вызовов растёт как сами числа Фибоначчи.

Лечится запоминанием уже посчитанного:

memo = {}
def fib(n):
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

print(fib(90))   # 2880067194370816120

Перебор вариантов

Главная сила рекурсии — перебор: перебрать все варианты, когда их структура «ветвится». Например, все двоичные строки длины n: на каждой позиции ставим 0 или 1 и рекурсивно заполняем остальное.

def binary(prefix, n):
    if len(prefix) == n:
        print(prefix)
        return
    binary(prefix + "0", n)
    binary(prefix + "1", n)

binary("", 3)    # 000 001 010 011 100 101 110 111

Из каждого вызова выходит две ветви, поэтому строк 2 ** n. Это много: при n = 20 уже миллион, при n = 40 — триллион. Перебором решают задачи, где n маленькое: в условии это обычно видно по ограничениям вроде n ≤ 20.

Похожим образом перебирают выборы «брать элемент или не брать», расстановки, пути — общая схема:

1. если текущий вариант собран целиком — обработать его;
2. иначе для каждого возможного следующего шага: сделать шаг, рекурсивно продолжить, отменить шаг.

Пункт «отменить шаг» важен, когда ты меняешь общий список: добавил элемент — после рекурсивного вызова убери его (pop).

Итог

• рекурсивная функция вызывает саму себя; у неё обязательно есть база и шаг;
• глубина ограничена (~1000), sys.setrecursionlimit поднимает предел;
• деление задачи пополам даёт маленькую глубину и быстрые алгоритмы;
• повторные вычисления лечатся запоминанием в словаре;
• рекурсивный перебор: сделай выбор → рекурсия → отмени выбор; число вариантов растёт очень быстро.