Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Kotlin: Tail Recursion Optimization

DZone's Guide to

Kotlin: Tail Recursion Optimization

Take a look at Kotlin's compiler and how it optimizes tail recursive calls using a simple example — as well as a couple of pitfalls to watch out for.

· Java Zone ·
Free Resource

Secure your Java app or API service quickly and easily with Okta's user authentication and authorization libraries. Developer accounts are free forever. Try Okta Instead.

The Kotlin compiler optimizes tail recursive calls — with a few catches. Consider a ranking 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 title

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 the tailrec modifier to a non-tail-recursive function does not generate compiler errors, though a warning does appear during the compilation step.

Secure your Java app or API service quickly and easily with Okta's user authentication and authorization libraries. Developer accounts are free forever. Try Okta Instead.

Topics:
java ,tail recursion ,kotlin ,tutorial

Published at DZone with permission of

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}