Что такое tail recurtion?

Что такое tail recursion

Tail recursion (хвостовая рекурсия) — это специальный тип рекурсии, где рекурсивный вызов является последней операцией функции. Это позволяет компилятору применить оптимизацию tail call optimization (TCO), которая превращает рекурсию в цикл.

Базовая концепция

Обычная рекурсия:

int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);  // Не tail recursion!
                                  // После вызова ещё умножение
}

После рекурсивного вызова factorial(n - 1) нужно выполнить умножение на n. Это значит, что функция должна ждать результата и продолжать работу.

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

int factorial_tail(int n, int accumulator = 1) {
    if (n == 0) return accumulator;
    return factorial_tail(n - 1, n * accumulator);
    // Tail recursion! Последняя операция — вызов функции
}

Здесь рекурсивный вызов — последняя инструкция. Компилятор может переиспользовать stack frame.

Как работает TCO

Без оптимизации (обычная рекурсия):

factorial(5)
  -> 5 * factorial(4)
     -> 4 * factorial(3)
        -> 3 * factorial(2)
           -> 2 * factorial(1)
              -> 1 * factorial(0)
                 -> return 1
              -> return 2 * 1 = 2
           -> return 3 * 2 = 6
        -> return 4 * 6 = 24
     -> return 5 * 24 = 120

// Stack frame существует для каждого уровня
// Максимальная глубина стека: O(n)

С TCO (хвостовая рекурсия):

factorial_tail(5, 1)
  -> factorial_tail(4, 5)
     -> factorial_tail(3, 20)
        -> factorial_tail(2, 60)
           -> factorial_tail(1, 120)
              -> factorial_tail(0, 120)
                 -> return 120

// Компилятор переиспользует один stack frame
// Максимальная глубина стека: O(1)

Компилятор просто переписывает параметры в существующем frame и прыгает на начало функции.

Эквивалентный цикл

Хвостовая рекурсия легко превращается в цикл:

// Хвостовая рекурсия
int factorial_tail(int n, int acc = 1) {
    if (n == 0) return acc;
    return factorial_tail(n - 1, n * acc);
}

// Эквивалентный цикл
int factorial_loop(int n) {
    int acc = 1;
    while (n > 0) {
        acc *= n;
        n--;
    }
    return acc;
}

Это ровно то же самое — компилятор с TCO делает такое преобразование автоматически.

Примеры хвостовой рекурсии

Поиск в бинарном поиске:

int binary_search(const std::vector<int>& arr, int target, 
                   int left, int right) {
    if (left > right) return -1;
    
    int mid = (left + right) / 2;
    if (arr[mid] == target) return mid;
    
    if (arr[mid] < target) {
        return binary_search(arr, target, mid + 1, right);
        // Tail recursion!
    } else {
        return binary_search(arr, target, left, mid - 1);
        // Tail recursion!
    }
}

Обход связного списка:

void process_list(Node* node) {
    if (!node) return;
    
    process_data(node->data);
    return process_list(node->next);  // Tail recursion!
}

Условия для TCO

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

Поддержка TCO в разных языках/компиляторах

Практические рекомендации

1. Используйте TCO для рекурсивных алгоритмов, когда это возможно
2. Помните о компиляторах — MSVC может не оптимизировать TCO
3. Профилируйте — убедитесь, что оптимизация действительно произошла
4. Предпочитайте циклы если TCO не гарантирована — более портативно

Пример проверки

// Компилируем с максимальными оптимизациями
// g++ -O2 -S code.cpp
// Смотрим ассемблер — рекурсивный вызов должен быть jmp, а не call

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