JavaScript递归:超过了最大调用堆栈大小

JavaScript recursion: Maximum call stack size exceeded

本文关键字：调用 堆栈 过了 递归 JavaScript      更新时间：2023-09-26

我有一个递归函数，用于在画布上移动一些圆。覆盖的圆被放大（放大），所有其他圆被推开。推送的圆推送其他圆，依此类推，直到缩放完成。

我收到一个错误"超过了最大调用堆栈大小"，我理解这个问题，但我不知道如何解决。。。我发现了三种可能的解决递归问题的方法：

  1. 将递归改为迭代
  2. 使用记忆
  3. 使用SetTimeout

但我认为我不能使用它们：

  1. 由于需要的操作数量未知，我无法实现迭代
  2. 我对记忆理解不够好，但我认为它也不适合（或者也许我错了，有人可能会对我说不同的话？）
  3. 我不能使用SetTimeout，因为它应该在这个特定的动画中阻止函数调用

如何解决此问题？

// Pushes circles aside when some other circle leans on these circles (on zoom in)
var moveCirclesAside = function(circle1, circleToSkip, groupOfMoves) {
    var count = circles.length;
    for (var i = 0; i < count; i++) {
        // Skip the same circle
        if (i == circle1.i) {
            continue;
        }
        // Also skip the circle which was intended not to move any further
        if (circleToSkip != null && i == circleToSkip.i) {
            continue;
        }
        // Get second circle
        var circle2 = circles[i];
        // Calculate a distance between two circles
        var dx = circle2.x - circle1.x;
        var dy = circle2.y - circle1.y;
        var distance = Math.sqrt((dx * dx) + (dy * dy));
        // If circles already collided need to do some moving...
        if (distance <= circle1.r + circle2.r + OD.config.circleSpacing) {
            // Get collision angles
            var angle = Math.atan2(dy, dx);
            var sine = Math.sin(angle);
            var cosine = Math.cos(angle);
            // Some circle position calculation
            var x = OD.config.circleSpacing;
            var xb = x + (circle1.r + circle2.r);
            var yb = dy * cosine - dx * sine;
            // Save each state (move) of any circle to the stack for later rollback of the movement
            groupOfMoves.push(copyCircleByVal(circle2));
            // Move the circle
            circle2.x = circle1.x + (xb * cosine - yb * sine);
            circle2.y = circle1.y + (yb * cosine + xb * sine);
            // Make sure that circle won't go anywhere out of the canvas
            adjustCircleByBoundary(circle2);
            // If moved circle leans against some other circles make sure that they are moved accordingly
            // And such related moves must be grouped for correct rolback of moves later - so we pass 'groupOfMoves' var
            moveCirclesAside(circle2, circle1, groupOfMoves);
        }
    }
};

这种溢出并不奇怪，因为算法在迭代时会增加堆栈，但退出条件是不可预测的，操作没有严格本地化（它们对附近的圆圈有连锁效应），因此处理时间会很混乱。

我会重新考虑这个算法。考虑寻找两个最接近的圆，如果它们相距超过给定阈值，则中止。否则，将它们稍微分开并重复。

1） 由于需要的操作数量未知，我无法实现迭代；

好吧，我没有看过你的代码，但一般避免线性递归（这里有一个线性递归）看起来是这样的：

while (1 == 1) {
    if (breakcondition)
        break;
    doSomeCode()
}

因此，您不必像for-循环那样知道迭代的确切次数。

您不需要知道制定迭代解决方案所需的数量或操作。重点是用自己的JavaScript堆栈替换JavaScript堆栈。查看此答案以查看如何实现它的示例：链接

您可以在JavaScript中将Array对象用作堆栈，因为它支持push()和pop()。

附言：正如Jim的回答所暗示的，你通常可以找到一个不需要这么多递归级别的算法。

尽量确保递归步骤只针对大于基本情况的情况执行。例如在这里的快速排序：

function qsort(k){
if(k == []){
    return k;
}
if(k.length == 1){
    return k;
}
//pick random pivot
var p = Math.floor(Math.random()*k.length);
console.log("pivot is" +  p + "'n");
//set left and right iter
var l = 0; var r = k.length - 1;
while( l < r){
console.log('hi'n');
//move l until its element is bigger than pivot
while(k[l] < k[p] && l < k.length) {
    l++;
    console.log('h1i'n');
}
//move r until its element is smaller than pivot
while(k[r] > k[p] && r >= 0) {r--;
    console.log('h2i'n');
}
//swap k[l] with k[r]
var temp = k[l]; k[l] = k[r]; k[r] = temp;
}
if(l == r){
//swap k[l] with k[p]
temp = k[l]; k[l] = k[p]; k[p] = temp;
}

var lk = k.slice(0,p); var rk = k.slice(p,k.length);
console.log(lk);
console.log(rk);
if(lk.length > 1){
 lk = qsort(lk);
}
if(rk.length > 1){
 rk = qsort(rk);
}
result = lk.concat(rk);
console.log(result);
return result;
}
var k = [23,245,67,34,24];
var result = qsort(k);
console.log(result);
//document.write(result);

如果您使用的不是lk.length > 1，而是lk != []之类的东西，或者没有进行检查，它有时会给出超出调用堆栈大小的错误，有时会根据选择的枢轴而起作用。

有一个包可以解决递归堆栈溢出问题。

https://github.com/facing-dev/recursive-free

相关文章：