# 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?

Sep 9, 2020 · 4 min read

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.

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

Written by

Android Developer

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +800K followers.

Written by

Android Developer

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +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