Tail Recursion in Kotlin

When Kotlin was released it joined the exclusive list of programming languages that provides tail recursion like Scala or Racket.

This programming technique allows the compiler to optimize the bytecode by treating the recursion as if it was a plain loop. This optimization however, can only be done if the final action of the recursive function calls itself as the last operation it performs.

This language feature has 2 big advantages over standard recursion:

• there is no risk of stack overflow as the stack does not have to keep track of each intermediate recursion state
• you can write your code as using recursion but the compiler will transform it into a fast and efficient loop

For this, Kotlin provides a modifier function keyword named tailrec which marks the function as tail-recursive to hint the compiler to replace recursion with iteration.

Consider the classic factorial function:

This function yields the correct factorial for the given input parameter:

But the function is not tail recursive. As you can see on line 4, the final action of the recursive function does not just call itself, but instructs the compiler to store the accumulator of the result in the stack:

If you invoke call factorial(5), the stack will look like this:

Now let’s see how you write the factorial function as tail recursive:

Notice the following:

• the tailrec keyword modifier has been added to the function signature
• the recursive call keeps track of the intermediate results with an accumulator variable that is passed as second argument