How to Use tailrec in Kotlin for Efficient Recursion

In Kotlin, use the tailrec modifier before a recursive function to enable tail call optimization, which prevents stack overflow by reusing the current function's stack frame. The function must call itself as its last operation for tailrec to work.

Syntax

The tailrec modifier is placed before a recursive function declaration. It tells Kotlin to optimize the recursion by converting it into a loop internally.

• tailrec: keyword to enable tail call optimization
• Function declaration: must be recursive
• Recursive call: must be the last action in the function

kotlin

tailrec fun factorial(n: Int, acc: Int = 1): Int {
    return if (n <= 1) acc else factorial(n - 1, acc * n)
}

Example

This example shows a tailrec function calculating factorial. It uses an accumulator to carry the result and calls itself last, allowing Kotlin to optimize the recursion.

kotlin

tailrec fun factorial(n: Int, acc: Int = 1): Int {
    return if (n <= 1) acc else factorial(n - 1, acc * n)
}

fun main() {
    println(factorial(5))
}

Output

120

Common Pitfalls

Common mistakes include:

• Not making the recursive call the last operation, so tailrec cannot optimize.
• Using tailrec on functions that do not call themselves directly.
• Expecting tailrec to work with mutual recursion (calls between different functions).

Here is a wrong and right example:

kotlin

// Wrong: recursive call is not last
fun wrongFactorial(n: Int): Int {
    val result = if (n <= 1) 1 else n * wrongFactorial(n - 1)
    return result
}

// Right: recursive call is last
tailrec fun rightFactorial(n: Int, acc: Int = 1): Int {
    return if (n <= 1) acc else rightFactorial(n - 1, acc * n)
}

Quick Reference

Tips for using tailrec in Kotlin:

• Use tailrec only on functions that call themselves as the last step.
• Use an accumulator parameter to carry intermediate results.
• Check compiler warnings if tailrec is ignored.
• tailrec helps avoid stack overflow in deep recursion.

Key Takeaways

Use the tailrec modifier to optimize recursive functions in Kotlin.

The recursive call must be the last operation for tailrec to work.

Use accumulator parameters to maintain state across recursive calls.

tailrec prevents stack overflow by converting recursion into iteration.

The Kotlin compiler ignores tailrec if the function is not properly tail-recursive.