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

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

Пример хвостовой рекурсии на Python (хотя стандартный интерпретатор CPython не оптимизирует хвостовую рекурсию):

def factorial_tail(n, acc=1):
    if n == 0:
        return acc
    return factorial_tail(n-1, acc * n)

print(factorial_tail(5))  # 120

Здесь factorial_tail вызывает себя в конце функции, передавая накопленное значение acc. Такой подход удобен для оптимизации в языках, поддерживающих хвостовую оптимизацию.