Recursión de JavaScript: el tamaño máximo de pila de llamadas superó

Question

Tengo una función recursiva para mover algunos círculos en un lienzo. El círculo sobredimensionado se agranda (acercar) y todos los otros círculos se alejan. Los círculos presionados empujan otros círculos y así sucesivamente hasta que se completa el zoom.

consigo un error "tamaño de la pila de llamadas máxima superado", y entiendo el problema, pero yo no sé cómo solucionarlo ... He encontrado tres posibles soluciones para resolver los problemas de recursividad en general:

1. Cambio recursividad para iteración
2. uso memoization
3. uso SetTimeout

Pero creo que puedo usar ninguna de ellas:

1. No puedo poner en práctica iteración debido recuento desconocido de operaciones necesarias
2. No entiendo memoization bastante bien, pero creo que no encaja bien (o tal vez estoy equivocado y alguien me pudiera dicho de manera diferente?)
3. No puedo usar SetTimeout, porque debería estar bloqueando las llamadas a funciones en esta animación en particular.

¿Cómo puedo solucionar este problema?

// 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

No sorprende que se desborde porque el algoritmo aumenta la pila mientras itera pero la condición de salida es impredecible, las acciones no están estrechamente localizadas (tienen efectos en cadena en círculos cercanos), por lo que el tiempo de procesamiento será caótico .

Yo reconsideraría el algoritmo. Considera encontrar los dos círculos más cercanos, si están más separados que un umbral dado aparte, aborta. De lo contrario, sepárelos un poco y repita.

Answer 2

1) No puedo poner en práctica iteración debido recuento desconocido de operaciones necesarias;

Bueno, no he mirado el código, sino una evasión general de recurrencia lineal (que tienen una relación lineal aquí) se parece a esto:

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

Por lo que no tiene que saber la número exacto de iteraciones como en el caso del for - loop.

Answer 3

No necesita saber el número o las operaciones necesarias para que pueda hacer una solución iterativa. El punto es reemplazar la pila de JavaScript con una propia. Verifique esta respuesta para ver un ejemplo de cómo implementarla: Link

Puede usar un objeto Array como una pila en JavaScript dado que admite push() y pop().

PD: Como sugirió la respuesta de Jim, generalmente puede encontrar un algoritmo que no necesita tantos niveles de recursión.