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

Хвостовая рекурсия - это когда любой рекурсивный вызов является последней операцией перед возвратом из функции.

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

Если рекурсивный вызов является последней операцией перед выходом из вызывающей функции и результатом вызывающей функции должен стать результат, который вернёт рекурсивный вызов, сохранение контекста уже не имеет значения — ни параметры, ни локальные переменные уже использоваться не будут, а адрес возврата уже находится в стеке. Поэтому в такой ситуации вместо полноценного рекурсивного вызова функции можно просто заменить значения параметров в стеке и передать управление на точку входа. До тех пор, пока исполнение будет идти по этой рекурсивной ветви, будет, фактически, выполняться обычный цикл. Когда рекурсия завершится (то есть исполнение пройдёт по терминальной ветви и достигнет команды возврата из функции) возврат произойдёт сразу в исходную точку, откуда произошёл вызов рекурсивной функции. Таким образом, при любой глубине рекурсии стек переполнен не будет.

Пример рекурсивной функции для вычисления факториала, использующей хвостовую рекурсию:

int fac_times (int n, int acc) {
    return (n==0) ? acc : fac_times(n - 1, acc * n);
}
int factorial (int n) {
    return fac_times (n, 1);
}

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

int factorial (int n) {
    return (n==0) ? 1 : n*factorial(n-1);
}

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