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?
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).
So, what is wrong?
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.
How do we resolve this flaw?
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.
What is a tail-recursive function and how to create one?
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.
Translate a tail-recursive function to an iteration.
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
