JavaScript recursion: Maximum call stack size exceeded

Question

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:

1. Change recursion to iteration
2. Use memoization
3. Use SetTimeout

But I think that I can use none of them:

1. I can not implement iteration because of unknown count of operations needed
2. 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?)
3. I can not use SetTimeout, because it should be blocking function calls at this particular animation.

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);
        }
    }
};

Answer 1

1) I can not implement iteration because of unknown count of operations needed;

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.

Answer 2

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.

Answer 3

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

You can use an Array object as a stack in JavaScript since it supports push() and pop().

PS: As Jim's answer suggested, you can usually find an algorithm that doesn't need this many levels of recursion.

Answer 4

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 > 1 you 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.

Answer 5

There is a package to solve recursive stack overflow.

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