Рекурсивный Shuffle Algo бросает ошибку StackOverflow

Question

Это рекурсивная реализация Shuffle Fisher-Yates. Почему это вызывает ошибку StackOverflow, когда я даю ей всего лишь 10000 элементов?

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 
} 

StackTrace:

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

Фишера-Yates в рекурсивной системе будет делать один уровень для каждого элемента в массиве, для воспроизведения.

Переполнение стека произойдет задолго до 10 000 уровней вызовов.

Есть ли какая-то особая причина, почему вы не можете использовать версию while-loop? Это намного проще, быстрее и надежнее ..... Это 5-линейный алгоритм .... как цикл while.

---

EDIT. В качестве теста я написал следующее:

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

Упорядочить, где я получил исключение переполнения? Huh, никогда! Я предполагаю, что мой JIT скомпилировал его как цикл вместо рекурсии, и я убил процесс где-то за «1816130».

Answer 2

10000 большое количество, особенно потому, что вы обрабатываете массив из 10 000 элементов. Вы можете twick размер стека, используя параметр JVM -Xss.