Рекурсия и хвостовая оптимизация

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

«Рекурсия — это цикл, выраженный через доверие: функция верит, что меньшая версия задачи уже решена.»

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

def factorial(n: Int): Int =
  if n <= 1 then 1
  else n * factorial(n - 1)

println(factorial(5))  // 120

Каждый вызов factorial ждёт результата следующего, чтобы умножить. Это значит, что вызовы копятся в стеке. Для больших n стек переполнится — ошибка StackOverflowError.

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

Если рекурсивный вызов — последнее действие функции (ничего после него не делается), компилятор может превратить рекурсию в обычный цикл. Это называется хвостовая оптимизация (tail call optimization). Для этого результат накапливают в дополнительном параметре-аккумуляторе.

import scala.annotation.tailrec

@tailrec
def factorial(n: Int, acc: Int = 1): Int =
  if n <= 1 then acc
  else factorial(n - 1, acc * n)   // последнее действие — вызов себя

println(factorial(5))  // 120

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

обычная рекурсия:           хвостовая рекурсия:
  f(3) ждёт f(2)               f(3, 1)
    f(2) ждёт f(1)        ->   f(2, 3)
      f(1) = 1                 f(1, 6)
  стек растёт                  стек НЕ растёт (цикл)

Та же идея на Python ▶

# Рекурсия на Python (у CPython нет хвостовой оптимизации!)
def factorial(n, acc=1):
    if n <= 1:
        return acc
    return factorial(n - 1, acc * n)

print(factorial(5))   # 120

# Для больших n в Python лучше цикл, т.к. стек ограничен:
def factorial_loop(n):
    acc = 1
    for i in range(2, n + 1):
        acc *= i
    return acc
print(factorial_loop(10))  # 3628800

Как работает под капотом (JVM)

У JVM нет встроенной хвостовой оптимизации. Поэтому её делает компилятор Scala: когда он видит хвостовой вызов, он генерирует не новый вызов метода, а переход в начало того же метода (как goto) с обновлёнными параметрами. В байт-коде это превращается в обычный цикл — стек не растёт, ошибки переполнения не будет. Без @tailrec компилятор оптимизирует молча, но аннотация гарантирует проверку.

Частые ошибки

Думать, что любая рекурсия безопасна. Только хвостовая оптимизируется; обычная глубокая рекурсия переполнит стек.
Ставить операцию после рекурсивного вызова. n * factorial(n-1) не хвостовое: после вызова идёт умножение.
Не использовать @tailrec. Без неё легко случайно написать нехвостовую версию.

Best practices

Для рекурсии, которая может уйти глубоко, всегда добавляйте аккумулятор и @tailrec.
Помните: @tailrec — это страховка, она заставит компилятор проверить хвостовость.
Если хвостовую версию написать сложно, рассмотрите методы коллекций (foldLeft) вместо ручной рекурсии.

Когда рекурсия лучше цикла

В функциональном стиле рекурсия — естественный инструмент, потому что она не требует изменяемого счётчика. Многие структуры данных рекурсивны по своей природе: список — это голова плюс остаток-список, дерево — это узел плюс поддеревья. Описывать обработку таких структур рекурсией часто проще и нагляднее, чем циклом с ручным управлением состоянием. Код буквально повторяет форму данных.

Главное — держать в голове разницу между обычной и хвостовой рекурсией. Обычная копит вызовы в стеке и для глубоких данных небезопасна. Хвостовая, превращённая компилятором в цикл, безопасна при любой глубине. Аннотация @tailrec — ваш страж: она не даст случайно написать небезопасную версию, выдав ошибку компиляции. На практике для любой потенциально глубокой рекурсии стоит сразу проектировать хвостовой вариант с аккумулятором.

Полезное правило: если вы пишете рекурсию, которая теоретически может уйти на тысячи уровней вглубь, сразу проектируйте её хвостовой с аккумулятором и ставьте @tailrec. Для неглубокой рекурсии по небольшим структурам этим можно пренебречь ради читаемости. Умение различать эти два случая приходит с практикой и быстро становится автоматическим.

Итоги. Рекурсия заменяет циклы в ФП, но обычная рекурсия копит стек. Хвостовая рекурсия с аккумулятором и @tailrec превращается в цикл и безопасна. Дальше — классы и объекты.