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

Почему важна хвостовая рекурсия

Scala работает на JVM, а значит, в обычных условиях рекурсивные вызовы накапливаются в стеке вызовов. При слишком глубокой рекурсии это приведёт к StackOverflowError.

Хвостовая рекурсия решает эту проблему: компилятор Scala преобразует хвостовую рекурсию в цикл (tail call optimization, TCO). Это даёт два преимущества:

1. Экономия памяти.

2. Возможность безопасной глубокой рекурсии (например, для обработки больших коллекций).

Признаки хвостовой рекурсии

• **Рекурсивный вызов должен быть последним действием в функции.
  **
• Никакие вычисления не должны происходить после вызова рекурсивной функции.

Синтаксис и использование аннотации @tailrec

Аннотация @tailrec используется для того, чтобы заставить компилятор проверять, является ли функция действительно хвосторекурсивной. Если она таковой не является, компилятор выдаст ошибку.

import scala.annotation.tailrec

Пример: сумма чисел от 1 до n (обычная и хвостовая реализация)

Обычная рекурсия (НЕ хвостовая)

def sum(n: Int): Int = {
if (n == 0) 0
else n + sum(n - 1) // операция после рекурсивного вызова
}

Здесь после sum(n - 1) ещё идёт + n, то есть вызов не в хвосте.

Хвостовая реализация с аккумулятором

import scala.annotation.tailrec
def sumTailRec(n: Int): Int = {
@tailrec
def loop(x: Int, acc: Int): Int = {
if (x == 0) acc
else loop(x - 1, acc + x) // хвостовой вызов
}
loop(n, 0)
}

Здесь:

• acc — аккумулятор, который накапливает результат.

• loop вызывает сам себя в последней строке без дополнительных операций, это tail call.

Пример: факториал (tail recursive)

def factorial(n: Int): Int = {
@tailrec
def loop(x: Int, acc: Int): Int = {
if (x <= 1) acc
else loop(x - 1, acc \* x)
}
loop(n, 1)
}

Пример: проверка, является ли список палиндромом (без использования reverse)

def isPalindrome\[A\](list: List\[A\]): Boolean = {
@tailrec
def loop(xs: List\[A\], ys: List\[A\]): Boolean = {
(xs, ys) match {
case (Nil, Nil) => true
case (h1 :: t1, h2 :: t2) if h1 == h2 => loop(t1, t2)
case _ => false
}
}
loop(list, list.reverse)
}

Пример: tail recursive map

def mapTailRec\[A, B\](list: List\[A\], f: A => B): List\[B\] = {
@tailrec
def loop(xs: List\[A\], acc: List\[B\]): List\[B\] = xs match {
case Nil => acc.reverse
case h :: t => loop(t, f(h) :: acc)
}
loop(list, Nil)
}

Здесь используется аккумулятор в обратном порядке и reverse в конце.

Хвостовая рекурсия vs обычная

Особенности и ограничения

1. @tailrec работает только для локальных функций, то есть вложенных (или помеченных как final/private).

2. @tailrec не работает на анонимных функциях.

3. Рекурсивный вызов должен быть точно последним действием.

Любое логическое выражение после вызова ломает оптимизацию:

loop(x - 1, acc + x) + 1 // это уже НЕ хвостовой вызов

Почему компилятор требует @tailrec

Он не делает TCO по умолчанию без этой аннотации, потому что:

• Не все JVM-платформы гарантируют безопасную реализацию оптимизации.

• Лучше явно указать разработчику на некорректную реализацию, если она случайно не является хвостовой.

Сравнение на практике

Обычный рекурсивный factorial(10000) вызовет StackOverflow, а хвостовой factorialTailRec(10000) выполнится успешно.

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