java - 递归洗牌算法抛出 StackOverflow 错误

Question

这是 Fisher-Yates 洗牌的递归实现。为什么当我只给它 10000 个项目作为输入时它会抛出 StackOverflow 错误？

public static void main(String[] args)
{
    int[] array = algo3(10000);
}

public static int[] algo3(int n)
{
    int[] a = new int[n];
    for (int i = 0; i < a.length ; i++)
        a[i] = i;
    algo3(a, 0);
    return a;
}

public static void algo3(int[] a, int pos)
{
    if (pos == a.length - 1)
        return;
    int tmp = a[pos];
    int rand = randInt(pos,a.length); // line #27
    a[pos] = a[rand];
    a[rand] = tmp;
    algo3(a,pos + 1); // line #30
}

private static int randInt(int i, int j)
{
    return (int) (Math.random() * (j - i)) + i; // line #35
}

堆栈跟踪:

Exception in thread "main" java.lang.StackOverflowError
    at java.util.concurrent.atomic.AtomicLong.compareAndSet(Unknown Source)
    at java.util.Random.next(Unknown Source)
    at java.util.Random.nextDouble(Unknown Source)
    at java.lang.Math.random(Unknown Source)
    at nl.saxion.Week1.randInt(Week1.java:35)
    at nl.saxion.Week1.algo3(Week1.java:27)
    at nl.saxion.Week1.algo3(Week1.java:30)

Answer 1

递归系统中的 Fischer-Yates 将为数组中的每个成员做一个级别的洗牌。

堆栈溢出将在 10,000 级调用之前很久发生。

有什么特殊原因导致你不能使用 while-loop 版本吗？它更简单、更快、更可靠......它是一个 5 行算法......作为一个 while 循环。

---

编辑。作为测试，我写了以下内容:

private static final void recurse(int val) {
    System.out.println(val);
    recurse(val + 1);
}
public static void main(String[] args) {
    recurse(1);
}

想知道我在哪里得到溢出异常吗？嗯，从来没有!我猜想我的 JIT 将其编译为循环而不是递归，并且我在“1816130”之后的某个地方终止了该进程。