1. Введение
Рекурсия звучит как акт программного нарциссизма: функция смотрит в зеркало и зовёт себя ещё раз. Но на самом деле это очень дисциплинированная техника. Рекурсивная функция обязана следовать договору: у неё есть момент, когда она перестаёт вызывать себя, и есть правило, как она к этому моменту приближается. Эти два элемента и есть «база» и «шаг».
Если сказать максимально практично, рекурсия состоит из двух частей.
Первая часть — базовый случай (base case): ситуация, когда задача настолько маленькая, что ответ очевиден, и дальше вызывать себя не надо.
Вторая часть — рекурсивный шаг (recursive step): правило, как из текущей задачи сделать похожую, но меньшую, и вызвать функцию снова.
Схематично это можно представить так:
flowchart TD
A["Задача"] --> B{"Задача уже простая?"}
B -->|да| C["Ответ сразу (база)"]
B -->|нет| D["Решить «чуть меньшую» задачу рекурсией (шаг)"]
D --> E["Построить ответ для текущей задачи"]
2. Базовый случай: точка, где мы перестаём углубляться
Базовый случай — это не украшение и не «ну ладно, добавим if, чтобы компилятор не ругался». Это центральная часть рекурсивной функции. Он отвечает на вопрос: когда мы прекращаем самовызовы и начинаем возвращаться обратно по стеку вызовов. В прошлой лекции вы видели, что каждый вызов создаёт кадр стека; базовый случай — это место, где новые кадры перестают создаваться.
Самый простой пример — сумма чисел от 1 до n.
Пример: сумма от 1 до n — базовый случай
Начнём с определения: sum_to(n) возвращает 1 + 2 + ... + n. Тогда логично сказать:
- если n == 0, сумма равна 0 (это база),
- иначе sum_to(n) = n + sum_to(n - 1) (это шаг, о нём чуть позже).
Код базового случая выглядит так:
int sum_to(int n) {
if (n == 0) return 0; // база: сумма до 0 равна 0
return n + sum_to(n - 1);
}
Обратите внимание: базовый ответ 0 здесь не случайный. Это так называемый «нейтральный элемент» для сложения: если вы что-то складываете, то стартовать удобно с нуля.
Пример: факториал — базовый случай
Факториал n! — это 1 * 2 * 3 * ... * n. Логично:
- 0! = 1 — это база,
- n! = n * (n - 1)! — шаг.
long long factorial(int n) {
if (n == 0) return 1; // база: 0! = 1
return n * factorial(n - 1);
}
И снова: 1 тут не «потому что так в учебнике». Это нейтральный элемент для умножения. Если вы строите произведение, «пустое произведение» удобно считать равным 1.
База как «самый маленький кирпич» задачи
Удобная аналогия (и да, она чуть бытовая, но работает): представьте, что вы собираете мебель по инструкции. Рекурсивный шаг — это «собери меньший модуль, потом прикрути его сюда». Базовый случай — это «возьми одну доску». Если инструкция никогда не говорит «вот самая простая деталь, дальше не дели», вы будете бесконечно делить шкаф на половинки и так и не закрутите ни одного винта.
Таблица: как быстро подобрать базовый случай
| Задача | Что уменьшаем? | Базовый случай | Базовый ответ |
|---|---|---|---|
| Сумма 1..n | |
|
|
| Факториал n! | |
|
|
| НОД (gcd) | |
|
|
| Обход строки по индексу | |
|
«ничего не делаем» |
Последняя строка важна: не всегда «ответ» — это число. Иногда база — это просто момент, когда функция прекращает работу (например, печать символов).
3. Рекурсивный шаг: делаем задачу меньше и вызываем себя
Рекурсивный шаг — это часть, которая делает рекурсию рекурсией: мы берём исходную задачу и сводим её к такой же, но меньшей. Здесь важно не столько «вызвать себя», сколько изменить параметры так, чтобы мы двигались к базе. Если параметры не меняются (или меняются в неправильную сторону), функция будет вызывать себя бесконечно.
У рекурсивного шага обычно два компонента.
Первый компонент — получить результат меньшей задачи через самовызов.
Второй компонент — «достроить» результат для текущего уровня (например, прибавить n, умножить на n, вывести символ).
Шаблон рекурсивной функции
Ниже полезный «скелет» (не магия, просто привычный порядок мысли):
ReturnType f(Args...) {
if (base_condition) {
return base_value; // база
}
// уменьшаем задачу
auto smaller = f(modified_args); // шаг: самовызов
// достраиваем ответ
return combine(smaller, current_state);
}
Иногда «достройка» идёт до вызова, иногда после. Сегодня нам важно другое: шаг обязан вести к базе.
Пример: сумма sum_to(n) — шаг
int sum_to(int n) {
if (n == 0) return 0;
return n + sum_to(n - 1); // шаг: n уменьшается на 1
}
Здесь уменьшение очевидно: было n, стало n-1. Рано или поздно n дойдёт до нуля, и сработает база.
Пример: НОД (алгоритм Евклида) — шаг
НОД (gcd) удобно показать, потому что здесь рекурсия не «по одному числу», а по паре. База: когда b == 0, ответ — a. Шаг: заменить (a, b) на (b, a % b).
int gcd(int a, int b) {
if (b == 0) return a; // база
return gcd(b, a % b); // шаг: b уменьшается через остаток
}
Почему это «приближает к базе»? Потому что a % b по модулю меньше b (если b != 0), а значит второе число постепенно уменьшается и в какой-то момент станет 0.
4. Проверка сходимости: дойдём ли мы до базы
Очень легко написать рекурсию, которая выглядит красиво, но на самом деле никогда не остановится. Поэтому перед тем как радоваться, полезно задать себе «проверочные вопросы». Они звучат скучно, но экономят часы отладки и пару нервных клеток.
Во-первых, достижима ли база для всех допустимых входных данных? Если вы решили, что базовый случай n == 0, а пользователь может передать -5, то куда вы будете уменьшать? В минус бесконечность? Это не очень продуктивный карьерный план.
Во-вторых, уменьшается ли задача на каждом шаге? Если вы случайно написали sum_to(n + 1), база будет становиться всё дальше, а не ближе.
В-третьих, меняется ли параметр вообще? Рекурсивный шаг вида return f(n); — это практически 100% билет в «переполнение стека».
Посмотрим на две «плохие» версии, чтобы научиться их распознавать глазами.
Плохой пример: параметр не меняется
int sum_bad(int n) {
if (n == 0) return 0;
return n + sum_bad(n); // ОШИБКА: n не уменьшается
}
Это бесконечная рекурсия. База есть, но к ней никто не идёт.
Плохой пример: база недостижима
int sum_bad2(int n) {
if (n == 0) return 0;
return n + sum_bad2(n + 1); // ОШИБКА: n растёт, база всё дальше
}
Снова бесконечность: теперь база «убегает».
5. Почему без базы программа «падает»: стек не резиновый
Когда рекурсивная функция вызывает саму себя, происходит ровно то же, что и при вызове любой другой функции: создаётся новый кадр стека. И если вы забыли базу (или она недостижима), вы будете создавать кадры стека снова и снова, пока стек не закончится. В этот момент программа обычно аварийно завершается. Это тот самый случай, когда компьютер честно пытался выполнить вашу просьбу, но упёрся в физику: память под стек ограничена.
Важно понимать одну психологическую ловушку: рекурсия не «зацикливается» как while(true). В цикле у вас есть один кадр стека, и вы бесконечно выполняете тело. В рекурсии вы создаёте новые кадры — много, очень много, и это копится.
Визуализация: бесконечная лестница вызовов
Представим такую функцию без базы:
int boom(int n) {
return boom(n - 1); // базы нет
}
Вызов boom(3) приводит к цепочке:
boom(3) вызывает boom(2)
boom(2) вызывает boom(1)
boom(1) вызывает boom(0)
boom(0) вызывает boom(-1)
...
И так далее, пока стек не переполнится.
Мини-демонстрация: «рекурсия без базы»
Ниже пример, который компилируется, но логически обречён. Он полезен именно как иллюстрация:
int factorial_bad(int n) {
// базы нет -> бесконечные вызовы
return n * factorial_bad(n - 1);
}
Даже если вы вызовете factorial_bad(1), функция уйдёт в factorial_bad(0), потом factorial_bad(-1) и дальше вниз.
6. Практика: трассировка и мини-приложение
Когда вы только учитесь рекурсии, полезно иногда буквально «проигрывать» вызовы. Да, это похоже на настольную игру «Стек вызовов: издание для студентов», но оно того стоит. Главное — различать два этапа: что происходит до самовызова и что происходит после, когда мы возвращаемся обратно.
Мини-трассировка: как база и шаг работают
Возьмём sum_to(3):
int sum_to(int n) {
if (n == 0) return 0;
return n + sum_to(n - 1);
}
Трассировка:
sum_to(3) = 3 + sum_to(2)
sum_to(2) = 2 + sum_to(1)
sum_to(1) = 1 + sum_to(0)
sum_to(0) = 0 <-- база
дальше возврат:
sum_to(1) = 1 + 0 = 1
sum_to(2) = 2 + 1 = 3
sum_to(3) = 3 + 3 = 6
Это важно: хотя строка return n + sum_to(n - 1); стоит «одной линией», по факту сначала надо вычислить sum_to(n - 1), и только потом прибавить n.
Практический пример: рекурсивные команды в консольном приложении
Чтобы рекурсия не оставалась «одним факториалом на полке», давайте оформим её как маленький набор команд в одном приложении. Мы не будем усложнять ввод и делать «умный парсер» строк — достаточно простого меню на std::cin и нескольких функций. Смысл примера — увидеть, что рекурсивная функция выглядит как обычная функция и вызывается так же.
Рекурсивные функции
long long factorial(int n) {
if (n == 0) return 1;
return n * factorial(n - 1);
}
int sum_to(int n) {
if (n == 0) return 0;
return n + sum_to(n - 1);
}
main: простое меню
#include <iostream>
long long factorial(int n);
int sum_to(int n);
int main() {
int cmd = 0;
std::cin >> cmd;
if (cmd == 1) {
int n; std::cin >> n;
std::cout << factorial(n) << '\n'; // например: 120
} else if (cmd == 2) {
int n; std::cin >> n;
std::cout << sum_to(n) << '\n'; // например: 55
} else {
std::cout << "Unknown command\n"; // Unknown command
}
}
Здесь есть важная мысль: рекурсия — это не «особый режим C++». Это просто функция, которая вызывает себя.
7. Типичные ошибки
Ошибка №1: «я написал рекурсию, но базовый случай забыл».
Это самая частая причина «почему программа падает» у новичков. Код может выглядеть логично, компилироваться идеально, но при первом же запуске уйти в бесконечные вызовы и закончиться аварийно. Лечится просто и скучно: базовый случай пишется первым, ещё до того как вы придумываете шаг.
Ошибка №2: базовый случай есть, но он недостижим.
Классическая ситуация: база проверяет n == 0, но шаг делает n + 1 или вообще не меняет n. Формально база присутствует, но реального «пути к ней» нет. Хорошая привычка — мысленно спросить: «через сколько шагов я точно попаду в базу?» Если ответа нет, что-то не так.
Ошибка №3: неправильный базовый ответ (например, factorial(0) = 0).
Иногда база написана, шаг тоже уменьшает задачу, рекурсия завершается, но результат неверный. Обычно это означает, что базовый ответ выбран неправильно. Для суммы база почти всегда 0, для произведения почти всегда 1. Если перепутать, ошибки будут тихими: программа не упадёт, а будет выдавать неправильные числа.
Ошибка №4: рекурсивный шаг не уменьшает задачу «в нужной метрике».
Бывает, что параметр меняется, но не гарантирует приближение к базе. Например, вы уменьшаете n не на 1, а делаете что-то вроде n = n - 2, забыв, что n может быть нечётным, и база проверяется только на n == 0. В итоге для n == 1 рекурсия уедет в отрицательные числа. В таких местах важно заранее продумать допустимые входные значения и то, какая база действительно покрывает все случаи.
Ошибка №5: рекурсивный вызов стоит «не там», и вы не понимаете порядок выполнения.
Строка return n + f(n - 1); на вид простая, но вычисляется в два этапа: сначала f(n - 1), потом + n. Если вы пытаетесь печатать что-то «по ходу», легко перепутать момент, когда будет выполнен std::cout. Тут помогает трассировка «на пальцах»: выпишите 3–4 шага вызовов и возвратов и посмотрите, где вы реально находитесь — до вызова или на возврате.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ