如何使这个同步递归函数异步

Question

我有一个javascript函数,递归地遍历一棵树.它有两个"标志"变量,在函数本身的范围之上设置为false或true,因此如果在递归"walkTree"函数时将标志设置为true,则每次递归都是如此.另一方面,for循环可能存在带有返回的函数,如果有的话.我遇到的问题是当递归太多时我会收到错误.

我想通过使这个递归函数异步来防止这个问题,我已经尝试将for循环中的子walkTree()调用放入setTimeout,但我现在遇到的问题是函数的其余部分将被执行(并且可能会返回错误的值),然后完成其余的异步操作.那么我怎样才能使这个异步同时仍然确保返回正确的值(而不是递归中的顶级函数调用)？

正如您所看到的,函数的结尾使用了所有调用共享的flagB"variable",因此我们需要确保所有递归调用都已完成(并返回一些内容),然后才能检查这些条件.谢谢!

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

正如 alex vasi 所建议的，您可能需要考虑迭代树遍历而不是递归。但是，如果您的数据集很大并且处理数据需要花费大量时间，您的 UI 可能会冻结。因此，您可能仍然希望异步进行处理。

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

上面的代码片段异步迭代遍历，从而给 UI 一些时间来更新自身。

这是一个jsFiddle，您可以在其中注意到同步和异步遍历之间的区别。同步遍历会让浏览器冻结一小段时间，而异步版本则让浏览器在处理树时有一些喘息的时间。（代码有点乱，抱歉……）

编辑：更新了 jsFiddle