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
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)
}
I want to know why this function works in java and also in kotlin with
tailrec
but not in kotlin withouttailrec
?
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. 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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With