Рекурсия C++: как работает, примеры и когда лучше цикл

В программировании на C++ рекурсией называют вызов функцией самой себя с более простыми данными, пока задача не станет тривиальной. Рекурсивная функция должна иметь базовый случай, в котором она сразу возвращает значение, и шаг, приближающий каждое следующее обращение к нему. Без базового случая функция вызывает себя, пока не кончится память стека.

Программы ниже собраны Clang (zig c++ 0.16.0) по стандарту C++17 (-std=c++17): код стандартный, но проверен только в Clang. Вывод программы скопирован из консоли Windows, где для кириллицы нужна кодировка UTF-8 (команда chcp 65001). В листингах для краткости стоит using namespace std;, в больших проектах лучше писать std:: явно.

Что такое рекурсия в C++

Начать проще с факториала. Чтобы вычислить n!, умножают n на (n-1)!, а 1! равен 1. Второе равенство служит базовым случаем, первое рекурсивным шагом. В коде они записаны буквально:

#include <iostream>
using namespace std;

int factorial(int n) {
    if (n <= 1) {
        return 1;                       // базовый случай: новых обращений не нужно
    } else {
        return n * factorial(n - 1);    // шаг рекурсии: задача стала меньше на единицу
    }
}

int main() {
    cout << "0! = " << factorial(0) << endl;
    cout << "5! = " << factorial(5) << endl;
    cout << "12! = " << factorial(12) << endl;
    return 0;
}

Вывод программы:

0! = 1
5! = 120
12! = 479001600

Функция возвращает целое число типа int, поэтому предел здесь 12!: 13! = 6 227 020 800 в этот тип не помещается (разбор в разделе «Частые ошибки»). Условие n <= 1 вместо n == 1 нужно, чтобы для нуля функция тоже вернула 1 (по определению 0! = 1), а отрицательное число не запускало бесконечную цепочку. Если отрицательный аргумент для вас считается ошибкой, проверка нужна до вызова. Блок else после return можно убрать, работа функции от этого не изменится.

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

Каждый вызов получает на стеке отдельный кадр (stack frame): там лежат параметры, локальные переменные и адрес возврата. У каждого вызова свой n, переменные с одним именем в разных вызовах не связаны. Пока factorial(4) ждёт результат factorial(3), его кадр остаётся на стеке. Добавим вывод на входе и на выходе, и порядок выполнения станет виден:

#include <iostream>
using namespace std;

int factorial(int n) {
    cout << "вход n=" << n << endl;
    if (n <= 1) {
        return 1;
    }
    int result = n * factorial(n - 1);
    cout << "выход n=" << n << ", вернул " << result << endl;
    return result;
}

int main() {
    int answer = factorial(4);
    cout << "итог: " << answer << endl;
    return 0;
}

вход n=4
вход n=3
вход n=2
вход n=1
выход n=2, вернул 2
выход n=3, вернул 6
выход n=4, вернул 24
итог: 24

Сначала происходит спуск до n=1, потом управление возвращается назад, и каждый вызов умножает свой n на то, что вернул нижний. Для n=1 строки «выход» нет: этот вызов вернул 1 по базовому случаю до строки вывода. Число вызовов, которые ждут результата одновременно, называется глубиной рекурсии. Здесь она равна четырём.

Примеры рекурсивных функций

Сумма элементов массива

Сумма элементов массива равна первому элементу плюс сумма остальных. Массив хранится в vector, индекс i показывает, с какого места считать, а сам вектор передаётся по ссылке на константу: при передаче по значению каждый вызов копировал бы весь вектор. Так же передавайте строки (string) и другие контейнеры.

#include <iostream>
#include <vector>
using namespace std;

int sumFrom(const vector<int>& v, size_t i) {
    if (i == v.size()) {
        return 0;                       // элементов больше нет
    }
    return v[i] + sumFrom(v, i + 1);
}

int main() {
    vector<int> data = {3, 1, 4, 1, 5};
    cout << "элементов: " << data.size() << endl;
    cout << "сумма элементов: " << sumFrom(data, 0) << endl;
    return 0;
}

элементов: 5
сумма элементов: 14

Ханойские башни

Нужно перенести n дисков с одного стержня на другой, перекладывая по одному и не кладя большой диск на малый. Рекурсивная идея такая: перенести n-1 дисков на запасной стержень, переложить самый большой, затем перенести n-1 дисков поверх него.

#include <iostream>
using namespace std;

// Переносит n дисков со стержня from на стержень to, запасной стержень via
void hanoi(int n, char from, char to, char via) {
    if (n == 0) {
        return;
    }
    hanoi(n - 1, from, via, to);
    cout << n << ": " << from << " -> " << to << endl;
    hanoi(n - 1, via, to, from);
}

int main() {
    hanoi(3, 'A', 'C', 'B');
    return 0;
}

Число слева в выводе обозначает номер диска, у меньшего диска номер меньше:

1: A -> C
2: A -> B
1: C -> B
3: A -> C
1: B -> A
2: B -> C
1: A -> C

Для n дисков необходимо 2^n — 1 ходов: для трёх 7, для двадцати уже 1 048 575. Итеративное решение написать заметно сложнее, а рекурсивная функция занимает несколько строк. Деревья, каталоги файлов и другие вложенные структуры обходят тем же способом: в каждом узле рекурсия повторяется для его частей.

Числа Фибоначчи: где рекурсия тормозит

Последовательность F(n) = F(n-1) + F(n-2) переписывается в код один в один, поэтому Фибоначчи стал учебным примером. Брать его как первый пример рекурсии мы бы не стали: наивная версия пересчитывает предыдущие значения снова и снова. Ниже она и версия с запоминанием результатов в std::map. Обе считают свои вызовы в глобальной переменной:

#include <iostream>
#include <map>
using namespace std;

int calls = 0;                      // глобальный счётчик, нужен только для замера

int fib(int n) {
    calls++;
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

map<int, int> memo;

int fibMemo(int n) {
    calls++;
    if (n <= 1) {
        return n;
    }
    auto it = memo.find(n);
    if (it != memo.end()) {
        return it->second;          // это значение уже считали
    }
    int value = fibMemo(n - 1) + fibMemo(n - 2);
    memo[n] = value;
    return value;
}

int main() {
    cout << "fib(30) = " << fib(30) << ", вызовов: " << calls << endl;
    calls = 0;
    cout << "fibMemo(30) = " << fibMemo(30) << ", вызовов: " << calls << endl;
    return 0;
}

fib(30) = 832040, вызовов: 2692537
fibMemo(30) = 832040, вызовов: 59

Наивная функция сделала около 2,7 млн вызовов, версия с запоминанием 59. С каждым следующим n количество вызовов растёт примерно в 1,6 раза: для fib(40) их уже больше 330 млн. Такой приём называется мемоизацией.

Её можно реализовать и с помощью std::vector, динамического массива с доступом по индексу: для небольших n он проще std::map. Проще всего и намного быстрее рекурсии число Фибоначчи считает обычный цикл for с двумя переменными: он делает n итераций. В int помещаются числа только до F(46), для больших нужен long long.

Переполнение стека

Размер стека известен заранее. На Linux его ограничивает ulimit -s, по умолчанию 8 МБ, а на Windows размер записывает в исполняемый файл линковщик: у MSVC это 1 МБ. Когда он кончается, программа падает. Чтобы определить предел, напечатаем счётчик через каждые 10 000 вызовов:

#include <iostream>
using namespace std;

int countLevels(int n, int level) {
    if (n == 0) {
        return 0;
    }
    if (level % 10000 == 0) {
        cout << level << endl;          // endl сбрасывает буфер: строка успеет выйти до падения
    }
    return 1 + countLevels(n - 1, level + 1);
}

int main() {
    int total = countLevels(1000000, 1);
    cout << "всего уровней: " << total << endl;
    return 0;
}

Последние строки вывода при сборке без оптимизаций (-O0):

150000
160000
170000

Итоговой строки «всего уровней» нет: программа завершилась с кодом -1073741571, это 0xC00000FD, так Windows сообщает о переполнении стека. В Linux то же выглядит как Segmentation fault (core dumped). Предел зависит от размера стека и размера кадра. У бинарника, собранного через zig c++, в заголовке записано 16 МБ, отсюда предел между 170 000 и 180 000 уровней, около 100 байт на кадр при -O0. Тот же код с ключом линковщика -Wl,--stack,1048576 (1 МБ, как у MSVC) упал раньше 20 000 уровней, а с 8 МБ, как на Linux, между 80 000 и 90 000.

Поймать это через try и catch нельзя: исключения C++ тут нет, стандарт такое поведение не определяет. Если глубина зависит от входных данных, например от вложенности файла, который прислал пользователь, ограничьте её счётчиком или перепишите обход на цикл со своим std::stack. Он хранит данные в куче.

Хвостовая рекурсия

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

#include <iostream>
using namespace std;

int countTail(int n, int acc) {
    if (n == 0) {
        return acc;
    }
    return countTail(n - 1, acc + 1);   // последняя инструкция функции: вызов самой себя
}

int main() {
    cout << countTail(100000000, 0) << endl;
    return 0;
}

Компилятор вправе заменить такой вызов переходом внутри одной функции, тогда новые кадры на стеке не создаются. Однако стандарт C++ этого не требует, и результат зависит от флагов. Мы собрали программу с глубиной сто миллионов двумя способами: с -O0 она упала с тем же кодом 0xC00000FD, с -O2 напечатала

100000000

Полагаться на это в C++ не стоит: в отладочной сборке оптимизаций нет, и код, который в релизе работает, под отладчиком падает. Для глубины в миллионы сразу пишите цикл.

Рекурсия или цикл

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

Чтобы записать рекурсию в виде цикла, результат накапливают в переменной. Факториал через for занимает три строки и работает при любом допустимом n:

int result = 1;
for (int i = 2; i <= n; i++) {
    result *= i;
}

Подробнее о конструкциях цикла: циклы с условием: while, for и do while. Рекурсивный спуск применяют и для разбора формул: как разобрать математическое выражение.

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

Если в первом примере заменить factorial(12) на factorial(13), программа не упадёт, а выведет неверное число. При сборке с -O2 получилось так:

13! = 1932053504

Правильное 13! равно 6 227 020 800, в 32-битный int оно не входит. Формально переполнение знакового типа даёт неопределённое поведение, на практике чаще всего видно такой «обрезанный» результат. Чтобы получить верный результат для больших значений, возьмите long long: в нём помещается 20!. Остальные частые ошибки:

• нет базового случая или он недостижим: с условием n == 0 вместо n <= 1 вызов для -1 не остановится, пока не кончится стек;
• шаг не приближает к базовому случаю: factorial(n) вместо factorial(n - 1);
• забыт return перед рекурсивным вызовом: у функции, которая обязана вернуть значение, это неопределённое поведение, компилятор обычно предупреждает;
• состояние хранится в глобальной переменной: при повторном запуске счётчик не обнуляется, а в нескольких потоках он портится, передавайте состояние параметрами функции.

Частые вопросы

Что такое рекурсия в C++ простыми словами?

Рекурсивная функция вызывает саму себя на упрощённых данных, чтобы решить задачу. Факториал числа 5 сводится к факториалу 4, тот к факториалу 3, и так до единицы, где ответ известен без новых обращений.

Что такое базовый случай в рекурсии?

Условие, при котором функция возвращает значение и себя не вызывает. У factorial это n <= 1, у суммы элементов вектора i == v.size(). Если базовый случай не достигается, обращения идут до переполнения стека.

Сколько раз функция может вызывать сама себя?

Предел задаёт размер стека и размер кадра, сам язык его не ограничивает. У простой функции с двумя параметрами без оптимизаций (-O0) это от десяти тысяч вызовов при стеке 1 МБ до сотен тысяч при 16 МБ, у функции с большим локальным массивом заметно меньше. На Linux стек можно увеличить командой ulimit -s, но надёжнее сократить глубину.

Можно ли вызвать main рекурсивно?

Нет. Стандарт C++ запрещает использовать main внутри программы, в отличие от C, где это допустимо. Clang собирает такой вызов без замечаний и предупреждает о нём только с ключом -pedantic, но формально программа некорректна. Вынесите нужный код в отдельную функцию и вызывайте рекурсивно её.

Чем заменить рекурсию, если не хватает стека?

Обычным циклом, а для обхода деревьев и вложенных структур циклом со своим std::stack. Данные в нём лежат в куче, и глубина ограничена только доступной памятью.