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:

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)
}

@Test
fun 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:

👁 Image

A Kotlin equivalent of the type of bytecode that the Kotlin compiler generates is the following:

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