Поддерживает ли 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)
}

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

 Callum01 сент. 2011 г., 03:32
Надо импортировать аннотацию с пометкой "импорт scala.annotation.tailrec "

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

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

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

 Vadzim25 апр. 2013 г., 08:35
Также о монадических батутах:apocalisp.wordpress.com/2011/10/26/...
Решение Вопроса

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

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

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 может увидеть его реализованным ".

 Jon Harrop13 мар. 2016 г., 09:53
@Cubic: Нет, это были общие звонки. Арнольд также реализовал их в LLVM.
 Jon Harrop06 нояб. 2010 г., 17:04
Текущий статус этого прото 80% », Я неТ понять. Я думал, что Арнольд Швайгхофер полностью реализовал это при Джоне Розе.руководство лет назад?
 Cubic12 нояб. 2012 г., 23:11
@JanHarrop может быть, речь шла о хвостовой рекурсии, а не об общих вызовах?

когда функция является саморекурсивной.

Доказательство способности рекурсии хвоста.

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

 Giorgio15 февр. 2013 г., 12:42
Только в очень простых случаях, когда функция является саморекурсивной. ": Означает ли это, что при использовании продолжений можно легко исчерпать пространство стека?
 Jon Harrop13 мар. 2016 г., 09:58
@ Джорджио: Да ..

Ваш ответ на вопрос