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

Java-based (JDBC) data connectivity to SaaS, NoSQL, and Big Data. Download Now.

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.

Connect any Java based application to your SaaS data.  Over 100+ Java-based data source connectors.

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