Задание № 24 · ЕГЭ

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

Рекурсивный вызов как последняя операция функции

2 мин чтенияСложность: Обновлено 29 сентября 2026

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

Хвостовая рекурсияНазвание связано с тем, что рекурсивный вызов находится в «хвосте» функции — в самом конце её действий.

Вид рекурсии, в котором рекурсивный вызов является последней операцией функции. Результат этого вызова сразу возвращается вызывающей функции.

Как распознать

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

\[F(p)=F(p')\quad\text{для рекурсивного шага}\]

Здесь \(p'\) — новые параметры функции. Важно, что результат рекурсивного вызова возвращается без изменений. Поэтому вычисление можно рассматривать как последовательное изменение состояния, а не как накопление отложенных операций.

№

Пример

Функция вычисляет сумму чисел от \(1\) до \(n\), передавая уже накопленную сумму в параметре \(s\). При \(n=0\) она возвращает \(s\). В рекурсивной ветви вызов sum(n - 1, s + n) стоит последним, поэтому рекурсия хвостовая.

Python

def sum_tail(n, s=0):
    if n == 0:
        return s
    return sum_tail(n - 1, s + n)

Не путайте с обычной рекурсией

Вызов return n + sum(n - 1) не является хвостовым: после возврата из sum нужно прибавить \(n\). Аналогично, в return 2 * f(n - 1) после рекурсивного вызова остаётся умножение. Такая структура связана с размером дерева рекурсивных вызовов, но сама по себе не гарантирует хвостовую рекурсию.

Проверка

Какой фрагмент содержит хвостовую рекурсию?

Главное за минуту

Главное

Хвостовая рекурсия заканчивается рекурсивным вызовом без последующих операций.
Для распознавания ищите базовый случай и вызов функции, результат которого сразу возвращается.
return n + f(n - 1) — не хвостовая рекурсия, а return f(n - 1, ...) — хвостовая.