Рекурсивные алгоритмы: базовый случай и стек вызовов

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

В реальном мире примеры рекурсии встречаются повсюду:

• Два зеркала, поставленные друг напротив друга, образуют бесконечный коридор отражений;

• Эффект Дросте — на картине нарисована женщина, держащая ту же самую картину, на которой нарисована женщина...;

• Природные фракталы — ветка папоротника повторяет форму всего листа папоротника, а каждая снежинка состоит из лучей, повторяющих узор снежинки.

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

Любая корректная рекурсивная функция обязана состоять из двух непременных частей:

1. Базовый случай (условие остановки / тривиальный случай):

Условие, при котором функция НЕ вызывает саму себя, а сразу возвращает готовое числовое значение без рекурсии. Это аварийный тормоз, предотвращающий бесконечный цикл вызовов;

2. Шаг рекурсии (рекурсивный спуск):

Ветка алгоритма, где функция вызывает саму себя, но ОБЯЗАТЕЛЬНО с параметром, который приближает задачу к базовому случаю (например, уменьшает аргумент n на 1: f(n - 1)).

Классический пример — вычисление факториала $n! = n \cdot (n - 1)!$:

def factorial(n):

if n <= 1: # 1. Базовый случай

return 1

return n * factorial(n - 1) # 2. Шаг рекурсии

Когда функция вызывает саму себя, операционная система сохраняет в специальной области оперативной памяти — стеке вызовов (Call Stack) — состояние текущей функции: адрес возврата и значения локальных переменных.

Процесс выполнения factorial(3):

1. factorial(3) приостанавливается и запрашивает factorial(2) — кадр кладется в стек;

2. factorial(2) приостанавливается и запрашивает factorial(1) — второй кадр в стек;

3. factorial(1) доходит до базового случая n <= 1 и мгновенно возвращает 1 (вершина рекурсивного спуска);

4. Начинается рекурсивный подъем: управление возвращается в factorial(2), который вычисляет 2 · 1 = 2 и выталкивается из стека;

5. Управление возвращается в factorial(3), который считает 3 · 2 = 6 и выдает финальный ответ.

Ряд Фибоначчи: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...

Каждое следующее число равно сумме двух предыдущих: $F(n) = F(n-1) + F(n-2)$.

Наивная рекурсивная функция:

def fib(n):

return n

return fib(n - 1) + fib(n - 2)

ПРОБЛЕМА: дерево вызовов разрастается с экспоненциальной скоростью $O(2^n)$. Например, при вызове fib(40) функция вычисляется миллиарды раз, многократно решая одни и те же подзадачи. Для эффективного решения применяют динамическое программирование (мемоизацию) или обычный цикл for за время $O(n)$.