如何将这个同步递归函数变成异步的

Question

我有一个遍历树形结构的 JavaScript 函数，它使用了两个“标志”变量，这些变量在函数本身外部被设置为 false 或 true。因此，如果在“walkTree”函数递归过程中某一次将标志设置为 true，那么每次递归都会是 true。另一方面，如果 for 循环中发现某些东西，该函数也可能通过返回退出。我的问题是当递归次数太多时，我就会遇到错误。

我想通过让这个递归函数异步化来解决这个问题。我尝试将子 walkTree() 调用放入 for 循环中的 setTimeout 中，但我现在的问题是在异步处理完成之前，函数的其余部分将被执行（并可能返回错误的值）。那么，在保证返回正确值的同时如何异步处理呢？（而不是递归调用中的顶层函数调用）?

如您所见，函数的结尾使用了所有调用共享的 flagB “变量”，因此我们需要确保在顶层函数检查这些条件之前，所有递归调用都已完成（并返回某些内容）。谢谢！

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

}

- Loic Duros

---

异步函数无法直接返回有用的值，您需要提供一个回调函数作为参数。 - zzzzBov

你为什么不在循环之前检查元素（参数）是否有子元素？ - Headshota

在我的实际函数中，我正在执行 if (n.children != undefined && n.children.length > 0)。 - Loic Duros

我仍然不太清楚回调函数作为参数如何进行递归。我也不确定该如何做。谢谢。 - Loic Duros

不确定你的函数应该做什么，以及是否打算在函数外使用变量。该函数从未返回“something-special”，但您正在检查if语句中的返回值。 - pimvdb

刚刚编辑了一下，现在返回“something-special”。想法是有些变量在函数作用域之外，只需要在递归的所有调用中设置为true一次，以便在递归的顶层返回一些东西，但是如果我们想使用回调使其异步化，我不确定该怎么做。 - Loic Duros

Answer 1

使用超时来遍历树，真的吗？你考虑过使用迭代树遍历代替递归吗？

例如：

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

还可以参考这个stackoverflow问题和维基百科文章。

- alex vasi

---

谢谢，我会研究一下。我一直在尝试让这个递归函数工作，没有想到还有其他方法可以做到。 - Loic Duros

请注意，如果您的树非常庞大，为了防止UI冻结，您可能仍然希望采用异步解决方案。 - rap1ds

Answer 2

正如Alex Vasi所建议的那样，您可能希望考虑使用迭代树遍历而不是递归。但是，如果您的数据集非常庞大且处理数据需要很长时间，您的用户界面可能会冻结。因此，您仍然可能希望异步处理数据。

以下是对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

- rap1ds

---

啊！非常好，谢谢！我会尝试将其变成异步的，看看是否有助于 UI 的性能。谢谢！ - Loic Duros