Я бы хотел, чтобы некоторые функции были оптимизированы для хвостовой рекурсии. Функция будет исключать исключение stackoverflow без оптимизации.
Образец кода:
import scala.util.Try
import scala.annotation.tailrec
object Main {
val trials = 10
@tailrec
val gcd : (Int, Int) => Int = {
case (a,b) if (a == b) => a
case (a,b) if (a > b) => gcd (a-b,b)
case (a,b) if (b > a) => gcd (a, b-a)
}
def main(args : Array[String]) : Unit = {
testTailRec()
}
def testTailRec() {
val outputs : List[Boolean] = Range(0, trials).toList.map(_ + 6000) map { x =>
Try( gcd(x, 1) ).toOption.isDefined
}
outputTestResult(outputs)
}
def outputTestResult(source : List[Boolean]) = {
val failed = source.count(_ == false)
val initial = source.takeWhile(_ == false).length
println( s"totally $failed failures, $initial of which at the beginning")
}
}
Запуск будет производить следующий вывод:
[info] Running Main
[info] totally 2 failures, 2 of which at the beginning
Таким образом, первые два прогона выполняются без оптимизации и отбрасываются на полпути из-за исключения stackoveflow, и только последующие вызовы создают желаемый результат.
Существует обходное решение: вам нужно разогреть функцию с помощью поддельных прогонов, прежде чем использовать ее. Но это кажется неуклюжим и очень неудобным. Существуют ли какие-либо другие средства для обеспечения того, чтобы моя рекурсивная функция была оптимизирована для хвостовой рекурсии до ее запуска в первый раз?
Обновить:
Мне сказали использовать двухэтапное определение
@tailrec
def gcd_worker(a: Int, b: Int): Int = {
if (a == b) a
else if (a > b) gcd(a-b,b)
else gcd(a, b-a)
}
val gcd : (Int,Int) => Int = gcd_worker(_,_)
Я предпочитаю сохранять чистое определение функционального стиля, если это возможно.
Я не думаю, что @tailrec применяется к функции, определенной как val. Измените его на def и он будет работать без ошибок.
Из того, что я понимаю, @tailrec [1] должен быть на методе, а не на поле. Я смог заставить это быть хвостом рекурсивным в REPL, сделав следующее изменение:
@tailrec
def gcd(a: Int, b: Int): Int = {
if (a == b) a
else if (a > b) gcd(a-b,b)
else gcd(a, b-a)
}
[1] http://www.scala-lang.org/api/current/index.html#scala.annotation.tailrec