Объясните концепцию хвостовой рекурсии и ее отличие от обычной рекурсии.

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

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

Пример хвостовой рекурсии на C++:

int factorialTail(int n, int acc = 1) {
    if (n == 0) return acc;
    return factorialTail(n - 1, n * acc);
}

// Вызов: factorialTail(5) вернёт 120

Здесь рекурсивный вызов factorialTail — последний оператор в функции, что позволяет оптимизировать рекурсию.