Поддерживает ли Scala оптимизацию хвостовой рекурсии?
Поддерживает ли Scala оптимизацию хвостовой рекурсии?
Ответы на вопрос(4)
В 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.8 может также поставляться с библиотечной поддержкой батута, который является техникой для оптимизации взаимно рекурсивных функций.
Много информации о состоянии рекурсии Scala можно найти вРич Догертис блогом.
как говорили другие авторы. То есть хвостовая рекурсивная функция преобразуется компилятором в цикл (вызов метода преобразуется в переход), как видно из трассировки стека при запуске хвостовой рекурсивной функции.
Попробуйте следующий фрагмент:
def boom(n: Int): Nothing = if(n<=0) throw new Exception else boom(n-1)
boom(10)
и осмотрите трассировку стека. Он покажет только один вызов функции boom - поэтому скомпилированный байт-код не является рекурсивным.
Есть предложение, плавающее вокругреализовать хвостовые вызовы на уровне JVM - что, на мой взгляд, было бы замечательно, так как тогда JVM могла бы выполнять оптимизацию времени выполнения, а не просто оптимизацию времени компиляции кода - и это могло бы означать более гибкую хвостовую рекурсию. В основномtailcall invoke будет вести себя точно так же, как обычный методinvoke но сбросит стек вызывающегоЭто безопасно - спецификация JVM гласит, что стековые фреймы должны быть сохранены, поэтому JIT должен выполнить некоторый статический анализ кода, чтобы выяснить, будут ли стековые фреймы использоваться никогда.
Текущий статус этогопрото 80%, Я нене думаю, что это будет сделано вовремя для Java 7 (invokedynamic имеет больший приоритет, и реализация почти завершена), но Java 8 может увидеть его реализованным ".
когда функция является саморекурсивной.
Доказательство способности рекурсии хвоста.
Похоже, что Scala 2.8 может улучшить распознавание хвостовой рекурсии ».