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

Verify, standardize, and correct the Big 4 + more– name, email, phone and global addresses – try our Data Quality APIs now at Melissa Developer Portal!

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.

Developers! Quickly and easily gain access to the tools and information you need! Explore, test and combine our data quality APIs at Melissa Developer Portal – home to tools that save time and boost revenue. Our APIs verify, standardize, and correct the Big 4 + more – name, email, phone and global addresses – to ensure accurate delivery, prevent blacklisting and identify risks in real-time.

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