JavaScript 递归：超出最大调用堆栈大小
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/9497625/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
JavaScript recursion: Maximum call stack size exceeded
提问by fizis
I have a recursive function for moving some circles on a canvas. Overed circle is enlarged (zoom in) and all the other circles is pushed away. Pushed circles push other circles and so on until zooming is complete.
我有一个递归函数，用于在画布上移动一些圆圈。覆盖的圆圈被放大（放大），所有其他圆圈被推开。推动的圆圈推动其他圆圈，依此类推，直到缩放完成。
I get an error "Maximum call stack size exceeded", and I understand the problem, but I just don't know how to solve it... I found three possible solutions for solving recursion problems in general:
我收到一个错误“最大调用堆栈大小超出”，我明白这个问题，但我只是不知道如何解决它......我找到了三种可能的解决递归问题的一般解决方案：
- Change recursion to iteration
- Use memoization
- Use SetTimeout
- 将递归改为迭代
- 使用记忆功能
- 使用设置超时
But I think that I can use none of them:
但我认为我不能使用它们：
- I can not implement iteration because of unknown count of operations needed
- I don't understand memoization well enough, but I think it does not fit either (or maybe I'm wrong and someone could told me differently?)
- I can not use SetTimeout, because it should be blocking function calls at this particular animation.
- 由于需要的操作数未知，我无法实现迭代
- 我不太了解记忆，但我认为它也不适合（或者我错了，有人可能会以不同的方式告诉我？）
- 我不能使用 SetTimeout，因为它应该在这个特定的动画中阻塞函数调用。
How do I fix this problem?
我该如何解决这个问题？
// 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);
}
}
};
采纳答案by Jim Blackler
It doesn't surprise this overflows because the algorithm grows the stack as it iterates but the exit condition is unpredictable, actions are not tightly localized (they have knock-on effects to nearby circles), so processing time will be chaotic.
这种溢出并不奇怪，因为算法在迭代时会增加堆栈，但退出条件是不可预测的，动作没有严格本地化（它们对附近的圆圈有连锁反应），所以处理时间会很混乱。
I would reconsider the algorithm. Consider finding the two closest circles, if these are further apart than a given threshold apart, abort. Otherwise move them apart a little and repeat.
我会重新考虑算法。考虑找到两个最近的圆，如果它们比给定的阈值相距更远，则中止。否则将它们分开一点并重复。
回答by Stasik
1) I can not implement iteration because of unknown count of operations needed;
1）由于需要的操作数量未知，我无法实现迭代；
Well, I have not looked at your code, but a general avoidance of linear recursion (you have a linear one here) looks like this:
好吧，我没有看过你的代码，但是一般避免线性递归（你这里有一个线性递归）看起来像这样：
while (1 == 1) {
if (breakcondition)
break;
doSomeCode()
}
So you do not have to know the exact number of iterations like in the for- loop case.
因此，您不必像在for- 循环的情况下那样知道确切的迭代次数。
回答by Lycha
You don't need to know the number or operations needed for you to make an iterative solution. The point is to replace the JavaScript stack with one of your own. Check this answer to see an example how to implement it: Link
您不需要知道制作迭代解决方案所需的数量或操作。关键是用您自己的堆栈替换 JavaScript 堆栈。检查此答案以查看如何实现它的示例：链接
You can use an Array object as a stack in JavaScript since it supports push()and pop().
您可以将 Array 对象用作 JavaScript 中的堆栈，因为它支持push()和pop()。
PS: As Jim's answer suggested, you can usually find an algorithm that doesn't need this many levels of recursion.
PS：正如吉姆的回答所建议的那样，您通常可以找到一种不需要这么多递归级别的算法。
回答by Aditya Mittal
Try to make sure the recursion step is only done for greater than base case. For example in quicksort here:
尽量确保递归步骤只在大于基本情况下完成。例如在这里的快速排序：
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);
If instead of lk.length > 1you used something like lk != []or not have a check, it could sometimes give call stack size exceeded errors and sometimes work depending on which pivots got chosen.
如果不是lk.length > 1您使用类似lk != []或没有检查的东西，它有时会给出调用堆栈大小超出错误，有时会根据选择的支点来工作。
