Tail Recursion in Kotlin

Have you heard about the modifier keyword tailrec in Kotlin? Do you know the idea behind this interesting keyword and how it is used?

Lam Pham
Lam Pham
Sep 9, 2020 · 4 min read
Recursive gates
Image by Tuan Hung Nguyen from Pixabay

In Kotlin, there are a bunch of modifier keywords that are very useful in some use cases. Some of them are already well-known because of their high applicability such as: inline, inner, lateinit, reified, open, override etc. In contrast, several ones are not largely known because there is not often use case that requires these features.

In this article, we will discover such a keyword: tailrec, and what it provides.

According to the official documentation:

tailrec marks a function as tail-recursive (allowing the compiler to replace recursion with iteration)

Following this definition, there must be something wrong with a recursive function since the compiler has to replace it with an iteration (for loop for instance).

A recursion function will cause the stackOverflowError when the number of recursive-calls is significant enough.

Look at this function:

private fun factorial(n : Long) : Long {
return if (n == 1L) n
else n * factorial(n -1)
}

To calculate a factorial of a given n, there would be n factorial() functions that are executed. The thing is with i within n to 2 inclusive, all the factorial(i) functions will not be done without the result of factorial(i-1). Thus, the virtual machine will store these functions into the stack and invoke the last multiplication once the result is out. When the number of such functions crosses a certain threshold, we will get stackOverflowError.

Well, the idea is that each call has to be independently accomplished. However, the principle of a recursive function does not allow us to achieve that idea because it has to call itself no matter what. Thus, the solution is very simple: do not use recursion; and that is why, back to the definition above, it is replaced by its alternative : an iteration.

The problem arises again when certain people still prefer using the recursion over the iteration (this is one of the styles of functional programming). Therefore, we need help of the compiler to silently change that recursion into an iteration in compile time.

However, not all recursive functions are comprehensive for the compiler. It can only translate a tail-recursive function into an iteration.

A recursive function is tail-recursive when recursive call is the last thing executed by the function. In other words, to calculate f(n), f(n-1)must be the last thing to be executed:

private fun f(n : Long) : Long {
return if (n == 1L) n
else f(n -1)
}

Back to the factorial function, this is how we can turn it to be tail-recursive:

/**
* A tail-recursive function
*/

private fun factorial(n : Long, a : Long = 1) : Long {
return if (n == 1L) a
else factorial(n - 1, n * a)
}

Note that tail-recursive function does not help to avoid stackoverflowerror, it is only a style of recursion.

Once we have prepared the tail-recursive function, the last step is adding the modifier keyword tailrec in order for the compiler to convert it into an iteration.

/**
* a tail-recursive function with keyword tailrec
*/
private tailrec fun factorial(n : Long, a : Long = 1) : Long {
return if (n == 1L) a
else factorial(n - 1, n * a)
}

This is how the function looks like after being compiled:

private final long factorial(long n, long a) {
while(n != 1L) {
long var10000 = n - 1L;
a = n * a;
n = var10000;
}

return a;
}

As you can see, this is no longer a recursion but a while loop.

Sometimes, developers must choose between a clean or a performance code. However, in the case of tailrec, you have a clean code with the recursion style and the compiler takes care of the performance. Best of both worlds!

In Android and any other high-level products, we only work with high-level languages or frameworks, so algorithm is not often a concern for developers. Iteration is a straightforward and easy-to-implement solution, so people often think about it first instead of a recursion. That is the reason why tailrec is quite unnecessary in my opinion. However, the ideas of tail recursion and tailrec are still very interesting. It inspires us to understand further how a function and a stack work.

tailrec does not often appear in our daily coding, but it is worth understanding what it brings us.

Hope you find some useful information in this article.

Lam Pham

Get smarter at building your thing. Join The Startup’s +800K followers.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store