Wywołanie metody rekurencyjnej powoduje StackOverFlowError w kotlin, ale nie w java

Mam dwa prawie identyczny kod w java i kotlin

Jawa:

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)
}

Kod Java przechodzi test z ogromnym wejściem, ale kod kotlin powoduje, StackOverFlowErrorże chyba, że ​​dodałem tailrecsłowo kluczowe przed helperfunkcją w kotlin.

Chcę wiedzieć, dlaczego ta funkcja działa w Javie, a także w Kolinie, tailrecale bez Kotlina bez tailrec?

PS: wiem co tailrecrobię

Chcę wiedzieć, dlaczego ta funkcja działa w java, a także w kotlin z kotlin bez, tailrecale nie w kotlinie bez tailrec?

Krótka odpowiedź brzmi, ponieważ twoja metoda Kotlina jest „cięższa” niż metoda JAVA . Przy każdym wywołaniu wywołuje inną metodę, która „prowokuje” StackOverflowError. Zobacz więc bardziej szczegółowe wyjaśnienie poniżej.

Ekwiwalenty kodu bajtowego Java dla reverseString()

Sprawdziłem kod bajtu dla twoich metod odpowiednio w Kotlin i JAVA :

Kod bajtowy metody Kotlin w 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);
    }
}
...

Kod bajtowy metody JAVA w 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);
    }
}
...

Istnieją więc dwie główne różnice:

1. Intrinsics.checkParameterIsNotNull(s, "s")jest wywoływany dla każdego helper()w wersji Kotlin .
2. Wskaźniki lewy i prawy w metodzie JAVA są zwiększane, natomiast w Kotlinie tworzone są nowe indeksy dla każdego wywołania rekurencyjnego.

Przetestujmy, jak Intrinsics.checkParameterIsNotNull(s, "s")sam wpływa na zachowanie.

Przetestuj obie implementacje

Stworzyłem prosty test dla obu przypadków:

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

I

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

W przypadku JAVA test powiódł się bez problemów, podczas gdy w przypadku Kotlin nie powiódł się z powodu błędu StackOverflowError. Jednakże, po dodaniu Intrinsics.checkParameterIsNotNull(s, "s")do JAVA sposób nie udało się także:

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);
}

Wniosek

Twoja metoda Kotlin ma mniejszą głębokość rekurencji, ponieważ wywołuje ją Intrinsics.checkParameterIsNotNull(s, "s")na każdym kroku, a zatem jest cięższa niż jej odpowiednik JAVA . Jeśli nie chcesz tej automatycznie generowanej metody, możesz wyłączyć sprawdzanie wartości NULL podczas kompilacji, zgodnie z odpowiedzią tutaj

Ponieważ jednak rozumiesz, co tailrecprzynosi korzyść (zamienia rekursywne wywołanie w iteracyjne), powinieneś go użyć.

Kotlin jest tylko trochę bardziej głodny na stosach (Int object params io int params). Oprócz rozwiązania tailrec, które tu pasuje, możesz wyeliminować zmienną lokalną temppoprzez 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)
}

Nie do końca wiadomo, czy to działa, aby usunąć zmienną lokalną.

Również eliminacja j może zrobić:

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)
}