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

Question

我有一个递归功能,可以在画布上移动一些圆圈.被遮挡的圆圈被放大(放大),所有其他圆圈被推开.推动圆圈推动其他圆圈,依此类推,直到缩放完成.

我得到一个错误"超出最大调用堆栈大小",我理解这个问题,但我只是不知道如何解决它...我找到了三种解决递归问题的可能解决方案:

1. 将递归更改为迭代
2. 使用memoization
3. 使用SetTimeout

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

1. 由于所需的操作数量未知,我无法实现迭代
2. 我不太了解memoization,但我认为它也不适合(或者我错了,有人可能会告诉我不同​​的？)
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);
        }
    }
};

Answer 1

1)由于需要的操作数量未知,我无法实现迭代;

好吧,我没有查看你的代码,但一般避免线性递归(这里你有一个线性的)看起来像这样:

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

因此,您不必知道for- 循环情况下的确切迭代次数.

Answer 2

这种溢出并不令人感到意外,因为算法在迭代时会增加堆栈,但退出条件是不可预测的,动作没有紧密定位(它们对附近的圆圈具有连锁效应),因此处理时间将是混乱的.

我会重新考虑这个算法.考虑找到两个最接近的圆圈,如果它们比分开的给定阈值更远,则中止.否则将它们分开并重复一遍.

Answer 3

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

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

PS：正如吉姆的回答所建议的，您通常可以找到一种不需要这么多递归级别的算法。