Компилятор Kotlin оптимизирует хвостовые рекурсивные вызовы с несколькими перехватами. Рассмотрим функцию ранга для поиска индекса элемента в отсортированном массиве, реализованную следующим образом с использованием хвостовой рекурсии и теста для нее:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
fun rank(k: Int, arr: Array<Int>): Int { tailrec fun rank(low: Int, high: Int): Int { if (low > high) { return -1 } val mid = (low + high) / 2 return when { (k < arr[mid]) -> rank(low, mid) (k > arr[mid]) -> rank(mid + 1, high) else -> mid } } return rank(0, arr.size - 1)}@Testfun rankTest() { val array = arrayOf(2, 4, 6, 9, 10, 11, 16, 17, 19, 20, 25) assertEquals(-1, rank(100, array)) assertEquals(0, rank(2, array)) assertEquals(2, rank(6, array)) assertEquals(5, rank(11, array)) assertEquals(10, rank(25, array))} |
IntelliJ предоставляет отличную функцию для отображения байт-кода любого кода Kotlin, в соответствии со следующим снимком экрана:
Эквивалент Kotlin типа байт-кода, который генерирует компилятор Kotlin, выглядит следующим образом:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
|
fun rankIter(k: Int, arr: Array<Int>): Int { fun rankIter(low: Int, high: Int): Int { var lo = low var hi = high while (lo <= hi) { val mid = (lo + hi)/2 if (k < arr[mid]) { hi = mid } else if (k > arr[mid]){ lo = mid + 1 } else { return mid } } return -1 } return rankIter(0, arr.size - 1)} |
хвостовые вызовы были переведены в простой цикл.
Есть несколько уловов, которые я мог видеть, хотя:
1. Компилятору должно быть явно сказано, какие вызовы являются хвостово-рекурсивными, с использованием модификатора tailrec.
2. Добавление модификатора tailrec к нерекурсивной функции не приводит к ошибкам компилятора, хотя на этапе компиляции появляется предупреждение
| Смотреть оригинальную статью здесь: Kotlin — оптимизация хвостовой рекурсии
Мнения, высказанные участниками Java Code Geeks, являются их собственными. |