javascript - 有没有更好的方法递归执行 shuffle 方法而不超过大型数组的最大调用堆栈？

Question

我正在尝试编写一个 RECURSIVE 函数来随机化/随机排列一个数组。

我编写的函数使用的是 Fisher-Yates shuffle 方法，该方法在小型数组上运行良好，但在包含 5000 个元素的预期数组上给出了“最大调用堆栈超出错误”

我想知道是否有人可以帮助我修复此方法，以便它仍然可以在更大的数组上递归工作？

下面是函数:

shuffleArray = (array, currentIndex=0) => {
    if (currentIndex >= array.length) {
      return array;
    }

    let randomIndex = Math.floor(Math.random() * currentIndex);

    let tempValue = array[currentIndex];
    array[currentIndex] = array[randomIndex];
    array[randomIndex] = tempValue;
    let newIndex = currentIndex += 1;
    return this.shuffleArray(array, newIndex);
  }

console.log(shuffleArray([1, 2, 3, 4, 5, 6]));
// returns a random array like [3,4,6,1,2,5]

console.log(shuffleArray([...Array(5000).keys()]));
// an example array of 5000 elements returns error: Uncaught RangeError: Maximum call stack size exceeded

Answer 1

像这样的任何循环:

for (let i = 0; i < n; i++) {
    // do something with i
}

可以毫无意义地递归地扩展到 O(log n) 空间:

function foo(start, end) {
    if (start + 1 === end) {
        // do something with start
    } else {
        let mid = start + Math.floor((end - start) / 2);
        foo(start, mid);
        foo(mid, end);
    }
}

foo(0, n);