Рекурсия

Рекурсия (recursion) — вызов в функции самой себя. Рекурсия заканчивается на граничном условии — значении, которое функция знает без нового вызова.

Зачем нужно

Многие объекты определяются через самих себя: $n!=(n-1)!\cdot n$. Рекурсивная функция повторяет такое определение почти дословно. Главный пример курса — Сортировка слиянием: отсортировать половины тем же способом и слить.

Как работает

Факториал

Определение: $0!=1$ (аксиома), $n!=(n-1)!\cdot n$ при $n\in \mathbb{N}$.

функ. factorial(n)
    если n = 0              // граничное условие
        return 1
    return n * factorial(n − 1)

Вызов раскрывается до граничного условия:

$f(n)=n\cdot f(n-1)=n(n-1)\cdot f(n-2)=\dots =n(n-1)\cdots 1\cdot f(0)=n!$

$T(N)=O(N)$.

Восходящая и нисходящая

	Аргумент	Пример	Граница
нисходящая	уменьшается	$f(n)=f(n-1)\cdot n$ → $n!$	$f(0)=1$
восходящая	увеличивается	$f(n)=2\cdot f(n+1)$ → $2^k$	$f(10)=1$

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

Не из лекции: восходящий пример

$f(n)=2^k\cdot f(n+k)$, до границы $k=10-n$ шагов, $f(n)=2^{10-n}$. При $n>10$ аргумент уходит от границы, и рекурсия не кончится.

Не из лекции: как доказывать рекурсию

Индукцией — той же, что стоит за рекурсивным определением. Для факториала: factorial(0) = 1 = 0!; если factorial(n − 1) = $(n-1)!$, то factorial(n) = $n\cdot (n-1)!=n!$.

Для рекурсии, которая делит задачу пополам, нужна сильная индукция по размеру: «для всех меньших размеров верно — значит, верно и для этого». Так доказывается Сортировка слиянием.

Стек вызовов и память

Не из лекции

Каждый вызов ждёт, пока вернётся вложенный, и держит свои переменные. Все незавершённые вызовы лежат на стеке вызовов (call stack). Память рекурсии — это её глубина, а не общее число вызовов:

	Вызовов всего	Глубина	Память стека
факториал	$N+1$	$N+1$	$O(N)$
сортировка слиянием	$2N-1$	$\lceil {\log }_{2}N\rceil +1$	$O(\log N)$

Стек небольшой: в Linux по умолчанию 8 МБ. Проверка на C++ (GCC 16, -O0): факториал с глубиной $2\cdot 10^5$ отрабатывает, с $10^6$ — падает с Segmentation fault. Циклом тот же факториал занимает $O(1)$ памяти. См. Время работы алгоритма.

Тонкости

• Граничное условие должно быть достижимо из любого допустимого аргумента. Нисходящий factorial(−1) до 0 не дойдёт, восходящий $f(11)$ до $f(10)$ — тоже.
• Каждый шаг должен строго приближать к границе. В сортировке слиянием это непустые половины: с базой right − left = 1 пустой отрезок $(0,0)$ вызывает сам себя бесконечно — см. L04.

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

• Забыть граничное условие или проверять его не тем сравнением (= 1 вместо ≤ 1).
• Считать, что рекурсия «бесплатна» по памяти: глубина $N$ — это $O(N)$ на стеке.
• Глубокая рекурсия там, где хватило бы цикла: падение по переполнению стека при $N\sim 10^6$.

Углубление — АиСД L05

Быстрая сортировка — рекурсия, в которой части неравные: их размеры зависят от того, куда встал опорный элемент. Отсюда разброс по глубине:

Разбиение	Глубина	Память стека
примерно пополам	$\approx {\log }_{2}N$	$O(\log N)$
одна часть всегда пустая	$N$	$O(N)$

Чтобы рекурсия кончалась, каждая часть должна быть строго короче отрезка. В схеме Ломуто это обеспечивает опорный элемент: он стоит на своём месте и в рекурсию не попадает. В схеме Хоара опорный не выкидывается, и короче части становятся только при правильном выборе середины — иначе на [1, 2] рекурсия бесконечна, см. L05.

Не из лекции

Худшую глубину можно убрать: рекурсивно сортировать только меньшую часть, а большую — циклом в том же вызове. Тогда каждый вложенный вызов получает не больше половины, и глубина $\le {\log }_{2}N$ на любом входе.

Углубление — АиСД L06

Рекурсия, которая вызывает себя дважды с перекрывающимися аргументами, пересчитывает одно и то же много раз:

функция fib(n)
    если n ≤ 2
        return 1
    иначе
        return fib(n − 1) + fib(n − 2)

fib(n − 2) вызывается и из fib(n), и из fib(n − 1), и так на каждом уровне. На лекции это рекурсивный способ: простой, но медленный («−» по времени в сравнении способов). Табличный и линейный способы считают каждое значение один раз — это уже Динамическое программирование.

Не из лекции

Вызовов у fib(n) ровно $2F_n-1$ — экспонента: fib(30) делает 1 664 079 вызовов. Та же беда у рекуррентного $c(n,k)$ для сочетаний: $c(30,15)$ — 310 235 039 вызовов. Глубина при этом всего $O(n)$, так что стек не переполнится — программа просто будет считать очень долго.

Отличие от сортировки слиянием, где тоже два вызова: там половины не пересекаются, и общий объём работы — $O(N\log N)$.