Рекурсия на блок-схемах

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

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

Звучит как замкнутый круг — функция зовёт функцию, та снова себя, и так до бесконечности? Нет. Секрет в том, что каждый новый вызов работает с меньшими данными и рано или поздно упирается в простейший случай, для которого ответ задан напрямую. На этом спуск останавливается, и ответы начинают «складываться» обратно.

Две обязательные части: база и шаг

У любой корректной рекурсии есть ровно два элемента. Без любого из них она ломается.

База рекурсии

База (или условие останова) — самый простой случай, ответ для которого мы знаем сразу, без вызова себя. Для факториала это $0! = 1$. Именно база не даёт рекурсии уйти в бесконечность.

Шаг рекурсии

Шаг — выражение задачи через её же уменьшенную версию. Факториал $n!$ выражается через $(n-1)!$ по формуле

$$ n! = n \cdot (n - 1)!. $$

То есть, чтобы посчитать $5!$, достаточно знать $4!$ и умножить его на $5$. А $4!$ выражается через $3!$, и так до базы $0! = 1$. Главное правило шага: аргумент должен приближаться к базе (здесь $n$ уменьшается на 1), иначе спуск никогда не закончится.

Факториал: разбор по шагам

Развернём вычисление $4!$ вручную. Сначала идёт «спуск» — вызовы откладываются, ожидая ответа от более простого случая:

4! = 4 * 3!
        3! = 3 * 2!
                2! = 2 * 1!
                        1! = 1 * 0!
                                0! = 1   <-- база, спуск остановлен

Затем «подъём» — ответы возвращаются снизу вверх и перемножаются:

0! = 1
1! = 1 * 1 = 1
2! = 2 * 1 = 2
3! = 3 * 2 = 6
4! = 4 * 6 = 24   <-- готовый ответ

На блок-схеме рекурсивная функция всегда начинается с ромба-проверки базы:

факториал(n):
   ( начало )
       |
   < n == 0 ? >---да---> ( возврат 1 )   // база
       | нет
   ||  факториал(n - 1)  ||              // вызов самой себя
       |
   [ R := n * результат ]
       |
   ( возврат R )                          // шаг

Тот же алгоритм на Python — запусти и сверь:

def factorial(n):
    if n == 0:        # база
        return 1
    return n * factorial(n - 1)   # шаг

for n in range(6):
    print(n, "! =", factorial(n))

Вывод:

0 ! = 1
1 ! = 1
2 ! = 2
3 ! = 6
4 ! = 24
5 ! = 120

Числа Фибоначчи

Второй классический пример — последовательность Фибоначчи, где каждое число равно сумме двух предыдущих:

$$ F(n) = F(n-1) + F(n-2), \quad F(0) = 0, \quad F(1) = 1. $$

Здесь две базы ($F(0)$ и $F(1)$) и шаг с двумя рекурсивными вызовами. Получается ряд $0, 1, 1, 2, 3, 5, 8, 13, \ldots$

def fib(n):
    if n < 2:         # две базы: F(0)=0, F(1)=1
        return n
    return fib(n - 1) + fib(n - 2)

print([fib(i) for i in range(10)])

Вывод:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Как это работает: стек вызовов на пальцах

Когда функция вызывает себя, не дойдя ещё до ответа, компьютер должен «запомнить», куда вернуться и какие были локальные значения. Для этого служит стек вызовов — стопка «карточек», работающая по принципу «последним вошёл — первым вышел» (LIFO).

Каждый новый вызов factorial кладёт сверху новую карточку со своим $n$. При вычислении $4!$ стопка дорастает до 5 карточек ($n = 4, 3, 2, 1, 0$). Как только сработала база, верхняя карточка отдаёт ответ и снимается, освобождая память; под ней лежащая карточка использует этот ответ — и так далее, пока стопка не опустеет.

Глубина рекурсии — это максимальная высота стопки. У факториала глубина равна $n + 1$. Если глубина становится огромной (например, забыли базу или $n$ слишком велик), стопка переполняет выделенную память — возникает ошибка переполнения стека (stack overflow), в Python это RecursionError.

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

Нет базы. Без условия останова рекурсия уходит в бесконечность и переполняет стек. База — обязательна.
Шаг не приближается к базе. Если вместо factorial(n - 1) написать factorial(n), аргумент не уменьшается — снова бесконечность.
Забыли вернуть результат вызова. Нужно именно return n * factorial(n - 1), а не просто вызвать функцию и потерять её ответ.
Недооценка стоимости. Наивный рекурсивный Фибоначчи пересчитывает одно и то же много раз: чтобы найти $F(n)$, требуется примерно $2^{n}$ вызовов, поэтому для больших $n$ он очень медленный.

Итоги

Рекурсия — функция вызывает саму себя для меньшей подзадачи.
Нужны база (известный ответ, останавливает спуск) и шаг (выражение через меньший случай, приближается к базе).
Факториал: $n! = n \cdot (n-1)!$, база $0! = 1$. Фибоначчи: $F(n) = F(n-1) + F(n-2)$, базы $F(0)=0$, $F(1)=1$.
Вызовы хранятся в стеке (LIFO): спуск наращивает стопку, подъём снимает карточки и собирает ответ.
Без базы или без движения к ней — переполнение стека.