Вызов рекурсивного метода вызывает StackOverFlowError в kotlin, но не в java

У меня есть два почти идентичных кода в Java и Kotlin

Ява:

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

Котлин:

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

Код Java проходит тест с огромным вводом, но код Kotlin вызывает, StackOverFlowErrorесли я не добавил tailrecключевое слово перед helperфункцией в Kotlin.

Я хочу знать, почему эта функция работает в Java, а также в Kolin с, tailrecно не в Kotlin без tailrec?

PS: я знаю, что tailrecделать

Я хочу знать, почему эта функция работает в Java, а также в Kotlin с, tailrecно не в Kotlin без tailrec?

Короткий ответ - потому что ваш метод Котлина "тяжелее", чем метод JAVA . При каждом вызове он вызывает другой метод, который «провоцирует» StackOverflowError. Итак, смотрите более подробное объяснение ниже.

Java байт-код эквиваленты для reverseString()

Я проверил байт-код для ваших методов в Kotlin и JAVA соответственно:

Байт-код метода Котлина в 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 в 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);
    }
}
...

Итак, есть 2 основных отличия:

1. Intrinsics.checkParameterIsNotNull(s, "s")вызывается для каждого helper()в версии Kotlin .
2. Левый и правый индексы в методе JAVA увеличиваются, тогда как в Kotlin новые индексы создаются для каждого рекурсивного вызова.

Итак, давайте проверим, как Intrinsics.checkParameterIsNotNull(s, "s")один влияет на поведение.

Протестируйте обе реализации

Я создал простой тест для обоих случаев:

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

А также

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

Для JAVA тест прошел без проблем, в то время как для Kotlin он провалился из-за a StackOverflowError. Однако, после того, как я добавил Intrinsics.checkParameterIsNotNull(s, "s")к методу JAVA, это также не удалось:

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

Вывод

Ваш метод Kotlin имеет меньшую глубину рекурсии, так как он вызывается Intrinsics.checkParameterIsNotNull(s, "s")на каждом шаге и, следовательно, тяжелее своего аналога JAVA . Если вам не нужен этот автоматически сгенерированный метод, вы можете отключить проверку на ноль во время компиляции, как здесь ответили

Однако, поскольку вы понимаете, какую пользу tailrecприносит (преобразует ваш рекурсивный вызов в итеративный), вы должны использовать его.

Kotlin просто чуть-чуть более требователен к стеку (параметры объекта Int и параметры типа int). Помимо подходящего здесь решения tailrec, вы можете исключить локальную переменную с tempпомощью 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)
}

Не совсем уверен, работает ли это, чтобы удалить локальную переменную.

Также устранение j может сделать:

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