Поддерживает ли Scala оптимизацию хвостовой рекурсии?

Как сказано в других плакатах, Scala выполняет оптимизацию хвостовой рекурсии во время компиляции. То есть хвостовая рекурсивная функция преобразуется компилятором в цикл (вызов метода преобразуется в переход), что можно увидеть из трассировки стека при запуске хвостовой рекурсивной функции.

Попробуйте следующий фрагмент:

def boom(n: Int): Nothing = if(n<=0) throw new Exception else boom(n-1)
boom(10)

и проверьте трассировку стека. Он покажет только один вызов функциональной стрелы, поэтому скомпилированный байт-код не является рекурсивным.

Существует предложение реализовать хвостовые вызовы на уровне JVM, что, на мой взгляд, было бы здорово, поскольку тогда JVM могла бы выполнять оптимизацию времени выполнения, а не просто оптимизировать время компиляции кода - и, возможно, могло бы означать более гибкую хвостовую рекурсию. По сути, tailcall invoke будет вести себя точно так же, как обычный метод invoke, но сбросит стек вызывающего, когда это будет безопасно - в спецификации JVM указано, что кадры стека должны быть сохранены, поэтому JIT должен выполнить некоторый статический анализ кода, чтобы выяснить, не собираются ли никогда не использовать кадры стека.

Текущий статус - proto 80%. Я не думаю, что это будет сделано вовремя для Java 7 (invokedynamic имеет больший приоритет, и реализация почти завершена), но Java 8 может увидеть это реализованным.

В Scala 2.8 вы можете использовать @tailrec для обозначения определенного метода, который, как вы ожидаете, оптимизирует компилятор:

import scala.annotation.tailrec

@tailrec def factorialAcc(acc: Int, n: Int): Int = {
  if (n <= 1) acc
  else factorialAcc(n * acc, n - 1)
}

Если метод не может быть оптимизирован, вы получите ошибку времени компиляции.

Scala 2.7.x поддерживает оптимизацию хвостового вызова для саморекурсии (вызывающей себя функции) конечных методов и локальных функций.

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

Много информации о состоянии рекурсии Scala можно найти в Блог Рича Догерти.

Только в очень простых случаях, когда функция является саморекурсивной.

Подтверждение способности хвостовой рекурсии.

Однако похоже, что Scala 2.8 может улучшить распознавание хвостовой рекурсии.