Récurrence JavaScript: taille maximale de la pile d'appels dépassée

J'ai une fonction récursive pour le déplacement de certains cercles sur une toile. Overed cercle est agrandie (zoom avant) et tous les autres cercles est repoussé.
Poussé cercles de pousser les autres cercles et ainsi de suite jusqu'à ce que le zoom est complète.

J'obtiens une erreur "le Maximum de la pile des appels taille dépassé", et je comprends le problème, mais je ne sais pas comment le résoudre...
J'ai trouvé trois solutions possibles pour résoudre les problèmes de la récursivité en général:

  1. Changer la récursivité à l'itération
  2. Utilisation memoization
  3. Utiliser SetTimeout

Mais je pense que je peux utiliser aucun d'entre eux:

  1. Je ne peux pas mettre en œuvre l'itération en raison de inconnu de comptage des opérations nécessaires
  2. Je ne comprends pas memoization assez bien, mais je pense qu'il ne convient d'ailleurs pas (ou peut-être que je me trompe et que quelqu'un pouvait m'a dit différemment?)
  3. Je ne peux pas utiliser SetTimeout, parce qu'il devrait être fonction de blocage des appels à cette animation particulière.

Comment puis-je résoudre ce problème?

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

source d'informationauteur fizis | 2012-02-29

  1. 5

    Il n'est pas étonnant que ce débordements, car l'algorithme augmente la pile comme il itère mais la condition de sortie est imprévisible, les actions ne sont pas étroitement localisée (ils ont des effets d'entraînement à proximité de cercles), de sorte que le temps de traitement sera chaotique.

    Je voudrais revoir l'algorithme. Trouver les deux plus proches des cercles, si ceux-ci sont plus séparés que d'un seuil donné, à part, abandonner. Sinon, écartez-les un peu et recommencez.

  2. 7

    1) je ne peux pas mettre en œuvre l'itération en raison de inconnu de comptage des opérations nécessaires;

    Bien, je n'ai pas regardé ton code, mais un évitement de linéaire de récursivité (vous avez un linéaire de un ici) ressemble à ceci:

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

    De sorte que vous n'avez pas à connaître le nombre exact d'itérations comme dans le for- boucle cas.

  3. 3

    Vous n'avez pas besoin de connaître le nombre ou les opérations nécessaires pour vous apporter une solution itérative. L'idée est de remplacer la pile JavaScript avec un de vos propres. Cochez cette réponse pour voir un exemple de comment la mettre en œuvre: Lien

    Vous pouvez utiliser un Tableau d'objet comme une pile en JavaScript car il prend en charge push() et pop().

    PS: Comme Jim réponse proposée, vous pouvez généralement trouver un algorithme qui n'a pas besoin de cela, de nombreux niveaux de récursivité.

  4. 0

    Essayez de vous assurer que la récursivité étape n'est effectuée pendant plus de cas de base. Par exemple, dans quicksort ici:

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

    Si, au lieu de lc.longueur > 1 vous avez utilisé quelque chose comme lc != [] ou de ne pas avoir un contrôle, il peut parfois donner de la pile des appels de la taille de dépassement des erreurs et parfois de travail en fonction qui pivote ai choisi.