L'appel de méthode récursive cause StackOverFlowError dans kotlin mais pas dans java

J'ai deux codes presque identiques en java et 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)
}

Le code java réussit le test avec une énorme entrée mais le code kotlin provoque un mot-clé StackOverFlowErrorsauf si j'ai ajouté tailrecavant la helperfonction dans kotlin.

Je veux savoir pourquoi cette fonction fonctionne en java et aussi en kolin avec tailrecmais pas en kotlin sans tailrec?

PS: je sais quoi tailrecfaire

Je veux savoir pourquoi cette fonction fonctionne en java et aussi en kotlin avec tailrecmais pas en kotlin sans tailrec?

La réponse courte est que votre méthode Kotlin est "plus lourde" que celle de JAVA . A chaque appel, il appelle une autre méthode qui "provoque" StackOverflowError. Donc, voyez une explication plus détaillée ci-dessous.

Équivalents de bytecode Java pour reverseString()

J'ai vérifié le code d'octet pour vos méthodes dans Kotlin et JAVA en conséquence:

Bytecode de la méthode Kotlin dans 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);
    }
}
...

Bytecode de la méthode JAVA dans 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);
    }
}
...

Donc, il y a 2 différences principales:

1. Intrinsics.checkParameterIsNotNull(s, "s")est invoqué pour chacun helper()dans la version Kotlin .
2. Les indices gauche et droit de la méthode JAVA sont incrémentés, tandis que dans Kotlin, de nouveaux indices sont créés pour chaque appel récursif.

Alors, testons comment Intrinsics.checkParameterIsNotNull(s, "s")seul affecte le comportement.

Testez les deux implémentations

J'ai créé un test simple pour les deux cas:

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

Et

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

Pour JAVA, le test a réussi sans problème tandis que pour Kotlin, il a lamentablement échoué en raison d'un StackOverflowError. Cependant, après avoir ajouté Intrinsics.checkParameterIsNotNull(s, "s")à la méthode JAVA , elle a également échoué:

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

Votre méthode Kotlin a une profondeur de récursivité plus petite car elle invoque Intrinsics.checkParameterIsNotNull(s, "s")à chaque étape et est donc plus lourde que son homologue JAVA . Si vous ne voulez pas de cette méthode générée automatiquement, vous pouvez désactiver les vérifications nulles pendant la compilation comme indiqué ici

Cependant, puisque vous comprenez quel avantage tailrecapporte (convertit votre appel récursif en appel itératif), vous devez utiliser celui-ci.

Kotlin est juste un peu plus gourmand en pile (paramètres d'objet int io paramètres int). Outre la solution tailrec qui convient ici, vous pouvez éliminer la variable locale temppar 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)
}

Je ne sais pas vraiment si cela fonctionne pour supprimer une variable locale.

L'élimination de j pourrait également faire:

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