Over a million developers have joined DZone.

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

Atomist automates your software deliver experience. It's how modern teams deliver modern software.

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

Get the open source Atomist Software Delivery Machine and start automating your delivery right there on your own laptop, today!

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