Последнее обновление：2026-10-12

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

Оптимизация хвостовой рекурсии — это специальная техника оптимизации, применимая к рекурсивным функциям; она позволяет значительно сократить потребление стековой памяти рекурсивными вызовами. Благодаря оптимизации хвостовой рекурсии компилятор может избежать создания нового стекового кадра при выполнении хвостового вызова, напрямую переиспользуя текущий кадр, что снижает риск переполнения стека и повышает производительность.

Что такое хвостовая рекурсия?¶

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

Пример не хвостовой рекурсии (числа Фибоначчи)¶

Приведённая вами функция fibonacci_non_tail() — стандартная реализация без хвостовой рекурсии:

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

В этой реализации после рекурсивных вызовов fibonacci_non_tail(n - 1) и fibonacci_non_tail(n - 2) ещё нужно сложить их результаты, поэтому это не хвостовая рекурсия. Каждый вызов требует сохранять контекстную информацию, чтобы продолжить вычисления после возврата из рекурсии, что приводит к быстрому росту использования стека.

Пример оптимизации хвостовой рекурсии¶

fibonacci_tail() использует хвостовую рекурсию:

int fibonacci_tail_helper(int n, int a, int b) {
    if (n == 0) {
        return a;
    }
    return fibonacci_tail_helper(n - 1, b, a + b);
}

int fibonacci_tail(int n) {
    return fibonacci_tail_helper(n, 0, 1);
}

Здесь fibonacci_tail_helper() — хвостовая рекурсия. Как видите, после рекурсивного вызова fibonacci_tail_helper(n - 1, b, a + b) функции больше не нужно делать никакой работы — она напрямую возвращает результат рекурсивного вызова. Поэтому рекурсивный вызов находится в «хвосте» функции, и никаких дополнительных действий после него выполнять не требуется.

Преимущества оптимизации хвостовой рекурсии¶

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

Тест производительности¶

Напоследок для описанного выше был проведён benchmark: оказалось, что оптимизация хвостовой рекурсии в этом сценарии весьма полезна — разница в производительности очень заметна!