Tail recursion in Kotlin

Learn the concept of tail recursion and how to get the most out of it in Kotlin.

The concept of tail recursion is not linked to Kotlin or any other specific language. It’s a generic concept, like standard recursion. Let’s start by reading a couple of examples of imperative and recursive iteration to get into context. We will work with the usual filter method present in almost all the modern and not-so-modern languages:

The imperative way

This is how a filter function could look in imperative style. (Let’s just ignore the fact that we could simply use the collection filter method that the Kotlin standard library provides.)

We start with an empty list and append all elements from the source list that satisfy the f predicate.

With this approach, we are managing the state inside the function instead of delegating that responsibility to the runtime. We need to create a mutable list and maintain it until the end of the loop to be able to return it.

It would be nice if we could handle this in a more functional style and remove the mutable state. To do that, we can go recursive.

The recursive way

This is how the filter function could look in recursive style:

This can be written in a shorter way leveraging some Kotlin expressions, but it is more readable like this for what is worth for this post.

Recursion allows us to delegate the list state to the runtime. We don’t need to create and maintain a mutable collection anymore; that’s handled in memory by the program runtime whenever the function stack gets evaluated. We limit ourselves to append an element on each recursion if it satisfies the f predicate.

That is nice, but recursion can also bring problems to the table. If the list was huge, we could get a StackOverFlowException. Historically, the call stack has been the main problem of the standard recursion for all the languages. It is an interesting programming style, but you need to know when and how to use it.

Let’s take a look at why we need to use the call stack for this type of recursion.

The need for a call stack

When the previous code snippet is evaluated at runtime, the language builds up a call stack gradually, the deeper it goes into the function. That is, to be able to rewind the stack once it reaches the last recursion.

The stack is needed because there are still operations to be done after the last recursion. In this case, the runtime replaces each recursion call in reverse order, from the deepest to the outermost, by its resulting list of elements. When it reaches the outermost level, it can actually call the method to build the list.

Makes sense, right? But there are ways to avoid this.

Removing the need for a call stack

We could build the list on each recursion and pass the temporary list to the next step, so the previous call in the stack becomes useless and can be discarded. If we do this for all the steps, we will reach the final recursion with the complete list already built, so there would be no need to rewind the stack anymore; therefore, no need for a stack.

That’s also called tail recursion, and we are talking about that in detail now.

The tail recursive way

Before explaining how we can tell the compiler to optimize a function that uses tail recursion, let’s take a look at the following example:

This function calls itself again as its last statement. It also appends to the resulting list instead of prepending to it. It builds the resulting list gradually on each recursion (res), so in the last recursion, the list will be complete and can be returned. There will be no more operations to run after this.

To be fair, tail recursion still builds the stack just because that’s the way the JVM works, but the already executed calls become useless right after they are executed. So the end case return value gets passed as it is during the whole rewind phase up to the outer most level.

Compiler optimization

This approach allows the compiler to optimize our recursive methods in some languages like Kotlin. The compiler optimization for tail recursive functions removes the possibility of overflowing your stack. What you get is stack-safe recursion.

To use this compiler optimization, you just need to tag your tail recursive function with the tailrec reserved word:

The compiler then translates this to a standard loop during compilation, and that’s always stack-safe since everything will occur under the same call inside the stack.

A good statement extracted from the Kotlin documentation that defines the requirements for a recursive function to be able to be declared as tailrec is the following:

To be eligible for the tailrec modifier, a function must call itself as the last operation it performs. You cannot use tail recursion when there is more code after the recursive call

Another important thing to notice is that we are just passing the resulting list as a parameter for all the recursions, so the state is not maintained by us or the runtime anymore but just removed forever. We just operate over input parameters to provide results. That’s the concept of pure functions in functional programming.

Here you have all the details about tail recursive functions from the official docs.

Extra bullet

Some languages do not support tail recursion compiler optimization. Some of those use a technique called “trampolining” to emulate this behavior. This technique is based on returning a trampoline in your function, which is just a structure capable of running the same function again until it returns anything that is not a trampoline. That would emulate the end case of a recursion. At that point, the resulting value is taken as the overall resulting value for the whole chained function execution. This is also not stacking calls because when the current call is done, it dies to give birth to the next one, thanks to the trampoline.

Here you have a really interesting article about how you can use trampolines in Scala to achieve tail recursion for scenarios where you cannot use a normal tailrec (like recursions with 2 or more functions).

Follow me

If you like this content, please take the time to follow me. See you around! 👋

• Twitter

• Bluesky

• LinkedIn

• Threads