Software Development

Kotlin – tail recursion optimization

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:

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

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.

Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
Back to top button