cómo hacer que esta función recursiva sincrónica sea asíncrona

Question

Tengo una función de javascript que recorre un árbol recursivamente. Tiene dos variables de "bandera" que se configuran como falsas o verdaderas por encima del alcance de la función en sí, de modo que si una bandera se configura como verdadera una vez mientras se está recursivamente la función "walkTree", será verdadera para cada recursión . Por otro lado, el bucle for podría existir la función con un retorno también si algo es para. El problema que tengo es que cuando hay demasiadas recurrencias obtengo un error.

Me gustaría evitar este problema al hacer que esta función recursiva sea asincrónica. He intentado poner la llamada sub walkTree() dentro del ciclo for en un setTimeout, pero el problema que tengo ahora es que el resto del la función se ejecutará (y puede devolver el valor incorrecto) antes de que el resto de las cosas asincrónicas se realice. Entonces, ¿cómo puedo hacer esto asíncrono mientras sigo asegurándome de que se devolverá el valor correcto (y no la llamada a la función superior en la recursión)?

Como puede ver, el final de la función utiliza esa "variable" flagB compartida por todas las llamadas, por lo que debemos asegurarnos de que todas las llamadas recursivas se hayan completado (y devuelto algo) antes de que el superior para estos condicionales. ¡Gracias!

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

Como sugirió alex vasi, es posible que desee considerar el cruce iterativo de árboles en lugar de recursivo. Sin embargo, si su conjunto de datos es enorme y el procesamiento de los datos lleva mucho tiempo, su IU puede congelarse. Por lo tanto, es posible que desee realizar el procesamiento de forma asincrónica.

Aquí es una modificación del ejemplo de Alex:

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

El fragmento de código anterior no Traverse iterativo de forma asíncrona, dando así tiempo para la interfaz de usuario para actualizarse.

Aquí hay un jsFiddle donde puede observar la diferencia entre la poligonal síncrona y asíncrona. La poligonal sincrónica hace que su navegador se congele durante un período de tiempo pequeño, mientras que la versión asíncrona le da al navegador un tiempo para respirar mientras procesa el árbol. (El código es un poco desordenado, lo siento ...)

Editar: Actualizado jsFiddle

Answer 2

¿Usar tiempos de espera para caminar en el árbol, en serio? ¿Ha considerado utilizar el cruce iterativo de árboles en lugar de recursivo?

Ejemplo:

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

Véase también this so question y wikipeida article.