jak zrobić tę synchroniczną funkcję rekurencyjną asynchroniczną

Question

Mam funkcję javascript, która przechadza się po drzewie rekursywnie. Ma dwie zmienne "flag", które są ustawione na false lub true powyżej zakresu samej funkcji, a więc jeśli flaga jest ustawiona na wartość true jeden raz, podczas gdy funkcja "walkTree" jest powtarzana, będzie to prawdziwe dla każdej rekursji . Z drugiej strony, pętla for mogłaby istnieć z funkcją powrotu, jeśli coś jest przeznaczone. Problemem, który mam, jest to, że w przypadku zbyt wielu rekursji pojawia się błąd.

Chciałbym zapobiec temu problemowi, czyniąc tę ​​funkcję rekursywną asynchroniczną, próbowałem umieścić wywołanie sub walkTree() wewnątrz pętli for w funkcji setTimeout, ale problem, który mam teraz, polega na tym, że reszta funkcja zostanie wykonana (i może zwrócić błędną wartość) zanim reszta asynchronicznych elementów zostanie wykonana. Jak mogę to zrobić asynchronicznie, jednocześnie upewniając się, że zwrócona zostanie prawidłowa wartość (a nie najwyższe wywołanie funkcji w rekursji)?

Jak widzisz, koniec funkcji wykorzystuje tę flagęB "zmienną" wspólną dla wszystkich wywołań, więc musimy upewnić się, że wszystkie rekursywne wywołania zostały zakończone (i zwrócone coś) zanim najwyższa kontrola dla tych warunkowych. Dzięki!

var flagA = false; 
var flagB = false; 

var walkTree = function (n) { 
    var sub; 

    for (var i = 0; i < n.children.length; i++) { 
     sub = walkTree(n.children[i]); 
     if (sub === 'something-special') { 
     return sub; 
     } 
    } 

    var test = doSomethingWith(n); 

    if (test === "something") { 
    flagA = true; 
    } 

    if (test === "something-else") { 
    flagB = true; 
    } 

    if (flagB === true) { 
    return true; 
    } 
    if (test === "something-special") { 
    return test; 
    } else { 
    return false; 
    } 

} 

Answer 1

Jak zasugerował alex vasi, możesz rozważyć iteracyjne przemierzanie drzew zamiast rekurencji. Jeśli jednak twój zbiór danych jest ogromny, a przetwarzanie danych zajmuje dużo czasu, Twój interfejs użytkownika może się zawiesić. Dlatego nadal możesz chcieć wykonać przetwarzanie asynchronicznie.

Oto modyfikacja przykład Alexa:

function asyncIterativeWalkTree(node) { 
    var queue = [node]; 

    var processQueue = function() { 
     var n = queue.shift(); 
     for (var i = 0; i < n.children.length; i++) { 
      queue.push(n.children[i]); 
      setTimeout(processQueue, 0); 
     } 
     doSomethingWith(n); 
    } 

    processQueue(); 
} 

Fragment kodu powyżej sposób iteracyjny trawers asynchronicznie, co daje trochę czasu na interfejsie użytkownika, aby zaktualizować siebie.

Oto jsFiddle, gdzie można zauważyć różnicę między przesuwem synchronicznym i asynchronicznym. Przesuwanie synchroniczne powoduje, że twoja przeglądarka zamarza przez krótki czas, podczas gdy wersja asynchroniczna daje przeglądarce czas na oddech podczas przetwarzania drzewa. (Kod jest nieco niechlujny, przepraszam ...)

Edycja: Zaktualizowane jsFiddle

Answer 2

Używanie limitów czasowych do poważnego spaceru po drzewie? Czy rozważałeś używanie iteracyjnego drzewa zamiast rekursywnego?

przykład:

var walkTree = function(node) { 
    var queue = [node]; 
    while (queue.length) { 
     var n = queue.shift(); 
     for (var i = 0; i < n.children.length; i++) { 
      queue.push(n.children[i]); 
     } 
     doSomethingWith(n); 
    } 
} 

patrz także this so question i wikipeida article.