Recursive method call cause StackOverFlowError in kotlin but not in java

Question

I have two almost identical code in java and kotlin

Java:

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

public void helper(char[] s, int left, int right) {
    if (left >= right) return;
    char tmp = s[left];
    s[left++] = s[right];
    s[right--] = tmp;
    helper(s, left, right);
}

Kotlin:

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

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

The java code pass the test with a huge input but the kotlin code cause a StackOverFlowError unless i added tailrec keyword before the helper function in kotlin.

I want to know why this function works in java and also in kolin with tailrec but not in kotlin without tailrec?

P.S: i know what tailrec do

When I tested these, I found that the Java version would work for array sizes up to around 29500, but the Kotlin version would stop around 18500. That's a significant difference, but not a very big one. If you need this to work for big arrays, the only good solution is to use `tailrec`, or avoid recursion; the stack size available varies between runs, between JVMs and set-ups, and depending on the method and its params. But if you're asking out of pure curiosity (a perfectly good reason!), then I'm not sure. You'd probably need to look at the bytecode. — gidds, Dec 23 '19 at 12:22

Anatolii · Accepted Answer · 2020-01-02T12:54:23.943

I want to know why this function works in java and also in kotlin with tailrec but not in kotlin without tailrec?

The short answer is because your Kotlin method is "heavier" than the JAVA one. At every call it calls another method that "provokes" StackOverflowError. So, see a more detailed explanation below.

Java bytecode equivalents for reverseString()

I checked the byte code for your methods in Kotlin and JAVA correspondingly:

Kotlin method bytecode in JAVA

...
public final void reverseString(@NotNull char[] s) {
    Intrinsics.checkParameterIsNotNull(s, "s");
    this.helper(0, ArraysKt.getLastIndex(s), s);
}

public final void helper(int i, int j, @NotNull char[] s) {
    Intrinsics.checkParameterIsNotNull(s, "s");
    if (i < j) {
        char t = s[j];
        s[j] = s[i];
        s[i] = t;
        this.helper(i + 1, j - 1, s);
    }
}
...

JAVA method bytecode in JAVA

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

public void helper(char[] s, int left, int right) {
    if (left < right) {
        char temp = s[left];
        s[left++] = s[right];
        s[right--] = temp;
        this.helper(left, right, s);
    }
}
...

So, there're 2 main differences:

Intrinsics.checkParameterIsNotNull(s, "s") is invoked for each helper() in the Kotlin version.
Left and right indices in JAVA method get incremented, while in Kotlin new indices are created for each recursive call.

So, let's test how Intrinsics.checkParameterIsNotNull(s, "s") alone affects the behavior.

Test both implementations

I've created a simple test for both cases:

@Test
public void testJavaImplementation() {
    char[] chars = new char[20000];
    new Example().reverseString(chars);
}

And

@Test
fun testKotlinImplementation() {
    val chars = CharArray(20000)
    Example().reverseString(chars)
}

For JAVA the test succeeded without problems while for Kotlin it failed miserably due to a StackOverflowError. However, after I added Intrinsics.checkParameterIsNotNull(s, "s") to the JAVA method it failed as well:

public void helper(char[] s, int left, int right) {
    Intrinsics.checkParameterIsNotNull(s, "s"); // add the same call here

    if (left >= right) return;
    char tmp = s[left];
    s[left] = s[right];
    s[right] = tmp;
    helper(s, left + 1, right - 1);
}

Conclusion

Your Kotlin method has a smaller recursion depth as it invokes Intrinsics.checkParameterIsNotNull(s, "s") at every step and thus is heavier than its JAVA counterpart. If you don't want this auto-generated method then you can disable null checks during compilation as answered here

However, since you understand what benefit tailrec brings (converts your recursive call into an iterative one) you should use that one.

@user207421 every method invocation has its own stack frame including `Intrinsics.checkParameterIsNotNull(...)`. Obviously, each such stack frame requires a certain amount of memory (for the `LocalVariableTable` and operand stack and so on).. — Anatolii, Jan 02 '20 at 22:29

Joop Eggen · Answer 2 · 2020-01-02T13:26:57.700

Kotlin is just a tiny bit more stack hungry (Int object params i.o. int params). Besides the tailrec solution which fits here, you can eliminate the local variable temp by xor-ing:

fun helper(i: Int, j: Int, s: CharArray) {
    if (i >= j) {
        return
    }               // i: a          j: b
    s[j] ^= s[i]    //               j: a^b
    s[i] ^= s[j]    // i: a^a^b == b
    s[j] ^= s[i]    //               j: a^b^b == a
    helper(i + 1, j - 1, s)
}

Not entirely sure whether this works to remove a local variable.

Also eliminating j might do:

fun reverseString(s: CharArray): Unit {
    helper(0, s)
}

fun helper(i: Int, s: CharArray) {
    if (i >= s.lastIndex - i) {
        return
    }
    val t = s[s.lastIndex - i]
    s[s.lastIndex - i] = s[i]
    s[i] = t
    helper(i + 1, s)
}

Recursive method call cause StackOverFlowError in kotlin but not in java

2 Answers2