Kotlin recursion vs Java Recursion

I was solving this problem in LeetCode which you should reverse a string. I used the Kotlin language to solve it and wrote a recursive function:

class Solution {
    fun rec(s: CharArray, i: Int, j: Int) {
        if (i >= j) return
        val t = s[j]
        s[j] = s[i]
        s[i] = t
        rec(s, i + 1, j - 1)

    fun reverseString(s: CharArray): Unit {
        rec(s, 0, s.lastIndex)

which works for the small test cases. But it fails to pass one of the test cases which is an array of ~53k elements. Then I looked at solutions and saw a Java solution which is identical to mine

class Solution {
    public void rec(char[] s, int i, int j) {
        if (i >= j) return;
        char tmp = s[i];
        s[i] = s[j];
        s[j] = tmp;
        rec(s, i + 1, j - 1);

    public void reverseString(char[] s) {
        rec(s, 0, s.length - 1);

This does pass all tests and is an acceptable answer to the solution.
Can someone explain why the Java solution passes but the Koltin one doesn’t?

P.S I know that using tailrec does solve the problem. Also, have tried to read the generated bytecode but I am not good at understanding it.

EDIT Forgot to mention that the kotlin solution fails by throwing Stackoverflow exception.

Thanks in advance.

Why in Kotlin you have thi call:

rec(s, i + 1, j - 1)

but in Java this one instead?

helper(s, i + 1, j - 1);

This is not a reasonable way to reverse a string. Stack space is limited in Java and Kotlin, and shouldn’t be wasted.

With a 50K character input, your call stack will get up to 25K calls deep. With the default 1MB stack size, that allows less than 40 bytes for each stack frame. It may fit in Java, but just. The Kotlin environment probably just has a few more methods on the stack when yours is called.

A good rule of thumb is that a practical recursive algorithm should use no more than O(log N) stack space for inputs of size N.

oops, that was a error in my side! renamed helper function to rec but forgot to fix the place it got called. sorry. :sweat_smile:

I know there are better ways to reverse a string. It just wanted to know why it works in Java and not in Kotlin just out of curiosity :smile: Thanks for explanation.

How it fails?

rec is a tailrec function :wink:

The Kotlin solutions fails by throwing StackOverflow exception

In the if you didn’t replace the i and j

1 Like

Java does have automatically tail call optimization(TCO) while Kotlin doesn’t, you’ve to mark your function with tailrec explicitly to enable the optimization.

That’s interesting. Can you prove somehow that Java optimizes those calls? When I made a test then I got java.lang.StackOverflowError in both Java & Kotlin unless I used tailrec modifier.

That is not true.

According to an article from 2014:

It’s important to note that this isn’t a bug in the JVM. It’s an optimization that can be implemented to help functional programmers who use recursion, which is much more common and normal in those languages. I recently spoke to Brian Goetz at Oracle about this optimization, and he said that it’s on a list of things to be added to the JVM, but it’s just not a high-priority item. For now, it’s best to make this optimization yourself, if you can, by avoiding deeply recursive functions when coding a functional language on the JVM.

Source: https://www.drdobbs.com/jvm/tail-call-optimization-and-java/240167044


I for one would not like an automatic tailrec optimization, because the optimization can be easily broken by even slight changes to the functions implementation. Suddenly the optimization would not be applied anymore at runtime. I like that Kotlin yields a compilation error when the function is declared tailrec without correct implementation.

The keyword serves as a documentation for my co-developers, too. They cannot accidentally break my tail recursion.