java堆栈溢出错误递归

Question

我正在制作一个方法，该方法将数组中的字符左右移动，并带有一个参数，该参数指示移动多少次。它必须在 20 毫秒内完成，所以我尝试了递归。

//数组中切换位置的方法

public static void bytt(char[] c, int i, int j){
    char temp = c[i];
    c[i] = c[j];
    c[j] = temp;
}

//这个方法左移

public static char rotasjon1(char[] a, int i){
    if(i > 0){
        bytt(a,i,i-1);
        return rotasjon1(a,i-1);
    }
    else
        return ' ';
}

//这个方法右移

public static char reverseRotasjon(char[] a, int i){
    if(i < a.length-1){
        bytt(a,i,i+1);
        return reverseRotasjon(a,i+1);
    }
    else
        return ' ';
}

//该方法根据参数决定使用右移还是左移

public static void rotasjon(final char[] a, int k){
    if(a.length == 1 || a.length == 0){
        return;
    }
    if(k >= 0){
        for(int i = 0; i< k; i++){
            char temp = a[a.length-1];
            rotasjon1(a,a.length-1);
            a[0] = temp;
        }
    }

    if(k < 0){
        for(int i = k; i< 0; i++) {
            char temp = a[0];
            reverseRotasjon(a, 0);
            a[a.length - 1] = temp;
        }
    }
}

//所有这些都适用于这个数组

char[] d = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'};
    char[] d0 = {'G', 'H', 'I', 'J', 'A', 'B', 'C', 'D', 'E', 'F'};

    Oblig1.rotasjon(d, 4);

d = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'};
    Oblig1.rotasjon(d, -6);

//但是我用这个数组得到java.lang.StackOverflowError

char[] x = new char[100_000];
    Oblig1.rotasjon(x, 99_999);

我知道数组很大，但是否有可能解决这个问题，还是我必须回到传统的 for 循环？它必须在 20 毫秒内执行

Answer 1

I know the array is big an stuff, but is it possible to fix this or do i have to go back to traditional for loops ?

异常是因为递归太深；即它需要太多的嵌套调用。

现在在许多语言中这都无关紧要。例如，使用典型的函数式语言，您可以根据需要深入递归。但有效的原因是函数式语言(和许多其他语言)实现了一种称为尾调用优化的东西，其中方法调用末尾的递归调用被(由编译器)优化为跳转到方法调用的开头方法。

引用:What Is Tail Call Optimization?

但是 Java 不支持尾调用优化。 (这有合理但复杂的原因。)相反，每次调用都会在当前线程的堆栈上获得一个堆栈帧；即 N 深度递归需要 N 个堆栈帧。问题在于 Java 线程具有固定数量的堆栈空间。 (默认值通常为 1M 字节或更少。)一旦创建，线程的堆栈就无法扩展。如果算法递归太深，线程会用完堆栈空间，JVM 会引发异常……如您所见。

那么答案是什么？

• 一般来说，避免在 Java 中实现可能深度递归的算法:

  • 如果算法是递归的，尝试将其转换为迭代等价物；例如手动进行尾调用优化。

  • 如果算法是迭代的，就这样吧!

• 如果您确实需要深度递归，您可以将线程的最大堆栈大小指定为构造函数参数。 (我不确定是否有架构限制，但你肯定会受到可用内存量的限制......)

if so, mabye you have some advice ? Remember it have to execute within 20 milliseconds.

• 如果您的主要目标是有效地实现它，请不要使用递归而不是迭代。在 Java 中 - 它不会更快，并且始终存在堆栈溢出的潜在风险。

• 在这种情况下，请查看使用临时数组和 System.arraycopy。 (如果以 1 为单位旋转，则不需要临时数组。您可以一次以 1 为步长以 N 为单位进行旋转，但效率很低。)

• 在这种情况下，看看如何实现它，就像您手动重新排列扑克牌一样……只用两只手(临时变量)。这在不使用 O(N) 额外存储的情况下提供了“按 N 旋转”问题的解决方案。