Что такое хвостовая рекурсия (tail recursion)?

Хвостовая рекурсия — это особый вид рекурсии, при котором рекурсивный вызов является последней операцией в функции (не считая возврата значения). Это позволяет компилятору выполнить оптимизацию хвостового вызова (Tail Call Optimization, TCO), преобразовав рекурсию в итеративный цикл, что исключает рост стека вызовов.

Пример хвостовой рекурсии (вычисление факториала):

// НЕ хвостовая рекурсия (после вызова есть операция умножения)
int factorial_bad(int n) {
    if (n <= 1) return 1;
    return n * factorial_bad(n - 1); // УМНОЖЕНИЕ после рекурсивного вызова
}

// ХВОСТОВАЯ рекурсия (аккумулятор передается как параметр)
int factorial_tail(int n, int accumulator = 1) {
    if (n <= 1) return accumulator;
    // Рекурсивный вызов — последняя операция, результат сразу возвращается.
    return factorial_tail(n - 1, n * accumulator);
}

Пример хвостовой рекурсии для обхода списка:

struct ListNode {
    int value;
    ListNode* next;
};

int sum_list_tail(ListNode* node, int current_sum = 0) {
    if (node == nullptr) return current_sum;
    return sum_list_tail(node->next, current_sum + node->value); // Хвостовой вызов
}

Ключевые моменты:

• Оптимизация: Компиляторы (например, GCC, Clang с флагами -O2, -O3) могут заменить хвостовой рекурсивный вызов на переход (jmp) вместо call, используя один и тот же стековый фрейм. Это предотвращает переполнение стека для глубокой рекурсии.
• Проверка: Не все рекурсивные алгоритмы легко преобразуются в хвостовую форму, иногда для этого требуется введение дополнительного параметра-аккумулятора.
• C++ и TCO: Стандарт C++ не гарантирует применение TCO, но все основные компиляторы выполняют эту оптимизацию при соответствующих настройках.