Olej писал(а):
если а). стоит квалификатор tailrec и б). это действительно хвостовая рекурсия (т.е. рекурсивный вызов - последний в последовательности операторов), то компилятор вместо рекурсивных вызовов превратит это примерно в следующее:
Вопрос относительно хвостовой рекурсии настолько интересный, что на нём стоит остановиться на время и уточниться...
Начиная с того, что традиционное вычисление факториала, которое показывают школьникам, вот на C, например:
Код: Выделить всё
int factorial (int n) {
return (n==0) ? 1 : n*factorial(n-1);
}
Оно
не является хвостовой рекурсией, т.к., хотя вызов factorial(n-1) и
записан последним, но
выполняется последним оператор
умножения на n.
Написал 2 маленьких тестовых программки на Kotlin:
- factr.kt - здесь
нет хвостовой рекурсии:
Код: Выделить всё
fun factorial(n: Long): Double {
return if (n == 0.toLong()) 1.toDouble() else n*factorial(n-1)
}
fun main( args: Array<String> ) {
val x = args[0].toLong()
println( factorial( x ) )
}
- factt.kt - здесь разворачивается хвостовая рекурсия:
Код: Выделить всё
tailrec fun fac_times(n: Long, acc: Long): Double {
return if (n == 0.toLong()) acc.toDouble() else fac_times(n - 1, acc * n)
}
fun factorial(n: Long): Double {
return fac_times(n, 1)
}
fun main( args: Array<String> ) {
val x = args[0].toLong()
println( factorial( x ) )
}
Выполняем:
Код: Выделить всё
[olej@dell tests]$ kotlinc factr.kt -include-runtime -d factr.jar
[olej@dell tests]$ kotlinc factt.kt -include-runtime -d factt.jar
[olej@dell tests]$ java -jar factr.jar 20
2.43290200817664E18
[olej@dell tests]$ java -jar factt.jar 20
2.43290200817664E18
А вот если я припишу tailrec в 1-ю реализацию:
Код: Выделить всё
tailrec fun factorial(n: Long): Double {
return if (n == 0.toLong()) 1.toDouble() else n*factorial(n-1)
}
...
То компилятор
очень лихо распознаёт эту ситуацию!:
Код: Выделить всё
[olej@dell tests]$ kotlinc factr.kt -include-runtime -d factr.jar
factr.kt:1:1: warning: a function is marked as tail-recursive but no tail calls are found
tailrec fun factorial(n: Long): Double {
^
factr.kt:2:53: warning: recursive call is not a tail call
return if (n == 0.toLong()) 1.toDouble() else n*factorial(n-1)
^