这是 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)
最佳答案
递归系统中的 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”之后的某个地方终止了该进程。
关于java - 递归洗牌算法抛出 StackOverflow 错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20084902/