Рекурсия и рекурсивные алгоритмы

Понятие рекурсии

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

Любое корректное рекурсивное определение состоит из двух частей: базовый случай (когда ответ известен сразу, без обращения к себе) и рекурсивный случай (сведение к меньшей задаче). Без базового случая рекурсия не остановится.

Пример: факториал

Факториал числа определяется так: 0! = 1 (база), n! = n * (n-1)! (рекурсия). На языке программирования:

def f(n):
if n == 0:
return 1
return n * f(n-1)

Вызов f(3) приводит к цепочке: 3 * f(2) = 3 * 2 * f(1) = 3 * 2 * 1 * f(0) = 3 * 2 * 1 * 1 = 6.

Как работает вызов

Шаг	Вычисление
f(3)	возвращает 3 * f(2)
f(2)	возвращает 2 * f(1)
f(1)	возвращает 1 * f(0)
f(0)	возвращает 1 (база)

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

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

Ещё один классический пример: F(1) = F(2) = 1, F(n) = F(n-1) + F(n-2). Рекурсия здесь наглядна, но неэффективна: одни и те же значения вычисляются много раз. Поэтому на практике часто заменяют рекурсию циклом.

Рекурсия и стек вызовов

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

Когда применять рекурсию

Рекурсия особенно удобна там, где задача по своей природе самоподобна: обход дерева каталогов, разбор вложенных скобок, построение фракталов, алгоритмы «разделяй и властвуй» (быстрая сортировка, двоичный поиск). В таких случаях рекурсивное решение проще и понятнее цикла.

Свойство	Рекурсия	Цикл
Запись	короче и нагляднее	длиннее
Память	расходует стек вызовов	экономнее
Риск	переполнение стека	зацикливание

Частые ошибки. Забытый базовый случай — программа уходит в бесконечную рекурсию и аварийно завершается переполнением стека. Неверное сведение, при котором задача не уменьшается. Слишком глубокая рекурсия для больших данных.

Анализ рекурсивной программы: значение, вывод и число вызовов

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

Оригинальный пример с возвратом значения

def value(n):
    if n <= 1:
        return 2
    return value(n - 1) + 3 * n

print(value(4))  # 29

Последовательно получаем value(1) = 2, value(2) = 2 + 6 = 8, value(3) = 8 + 9 = 17, value(4) = 17 + 12 = 29. Для входа 4 функция вызывается четыре раза. Слагаемые 3n вычисляются при возвращении из вложенных вызовов.

Порядок печати

def show(n):
    if n == 0:
        return
    print(n, end=' ')
    show(n - 1)
    print(n, end=' ')

show(3)  # 3 2 1 1 2 3

Первая печать идёт при углублении, вторая — при возвращении. Вызов show(0) выполняется, но ничего не печатает. Поэтому здесь четыре вызова и шесть напечатанных чисел.

Две рекурсивные ветви

Если при n > 0 функция вызывает себя дважды с n − 1, число всех вызовов удовлетворяет C(0) = 1, C(n) = 1 + 2C(n − 1). Отсюда C(1) = 3, C(2) = 7, C(3) = 15. Глубина при этом растёт линейно, а общее число вызовов — значительно быстрее. Нарисовать одну цепочку вместо дерева недостаточно.

Укажите допустимые входы. В show предполагается целое n ≥ 0: для отрицательного числа команда n − 1 удаляет от базы, и завершения по этому условию не будет. Не запускайте такой случай для проверки; сначала исследуйте изменение параметра.

Справочные материалы: Понятие рекурсии — исходная тема. Связанные уроки: Трассировка алгоритма по шагам, Алгоритмы и их эффективность.

Кратко о главном

• Рекурсия — определение алгоритма через вызов самого себя.
• Обязательны базовый случай и сведение к меньшей задаче.
• Классические примеры — факториал и числа Фибоначчи.
• Без базового случая рекурсия бесконечна и переполнит стек.