Kotlin compiler optimizes tail recursive calls with a few catches. Consider a rank function to search for the index of an element in a sorted array, implemented the following way using tail recursion and a test for it:
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 provides an awesome feature to show the bytecode of any Kotlin code, along the lines of the following screenshot:
A Kotlin equivalent of the type of bytecode that the Kotlin compiler generates is the following:
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)} |
the tail calls have been translated to a simple loop.
There are a few catches that I could see though:
1. The compiler has to be explicitly told which calls are tail-recursive using the “tailrec” modifier
2. Adding tailrec modifier to a non-tail-recursive function does not generate compiler errors, though a warning does appear during compilation step
| Published on Java Code Geeks with permission by Biju Kunjummen, partner at our JCG program. See the original article here: Kotlin – tail recursion optimization Opinions expressed by Java Code Geeks contributors are their own. |
