Ricorsione JavaScript: Dimensione massima stack di chiamate superata

Question

Ho una funzione ricorsiva per spostare alcuni cerchi su una tela. Il cerchio sovradimensionato viene ingrandito (ingrandito) e tutti gli altri cerchi vengono allontanati. I cerchi spinti spingono altri cerchi e così via finché lo zoom non è completo.

ottengo un errore "massima dimensione dello stack delle chiamate superato", e capisco il problema, ma io non so come risolverlo ... ho trovato tre possibili soluzioni per risolvere i problemi di ricorsività in generale:

1. Change ricorsione per iterazione
2. usa memoization
3. usa SetTimeout

Ma penso che posso usare nessuno di loro:

1. non posso implementare l'iterazione causa della sconosciuta conteggio delle operazioni necessarie
2. Non capisco Memoizzazione abbastanza bene, ma penso che non si adatta né (o forse mi sbaglio e qualcuno mi ha detto potuto in modo diverso?)
3. Non riesco a utilizzare SetTimeout, perché dovrebbe bloccare le chiamate di funzione in questa particolare animazione.

Come risolvere questo 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

Non sorprende questo overflow perché l'algoritmo aumenta lo stack mentre itera ma la condizione di uscita è imprevedibile, le azioni non sono localizzate strettamente (hanno effetti a catena nelle cerchie vicine), quindi il tempo di elaborazione sarà caotico .

Vorrei riconsiderare l'algoritmo. Considera di trovare i due cerchi più vicini, se questi sono più distanti di una certa soglia, abortire. Altrimenti spostali un po 'e ripeti.

Answer 2

1) Non posso attuare iterazione causa della sconosciuta conteggio delle operazioni necessarie;

Beh, non ho guardato il vostro codice, ma un rifiuto generale della ricorsione lineare (si dispone di un lineare qui) assomiglia a questo:

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

Quindi non c'è bisogno di conoscere la numero esatto di iterazioni come nel caso for - loop.

Answer 3

Non è necessario conoscere il numero o le operazioni necessarie per effettuare una soluzione iterativa. Il punto è sostituire lo stack JavaScript con uno dei tuoi. Controlla questa risposta per vedere un esempio su come implementarla: Link

È possibile utilizzare un oggetto Array come stack in JavaScript poiché supporta push() e pop().

PS: come suggerito dalla risposta di Jim, di solito è possibile trovare un algoritmo che non ha bisogno di questi numerosi livelli di ricorsione.