使用 setImmediate() 递归

Question

我有以下递归函数：

 function explore(v, componentN) {
    return function () {
        nodes[v].visited = true;
        nodes[v].componentNumber = componentN;
        preVisit(v);
        adjList[v].forEach((item) => {
            if (!nodes[item].visited){
                ex(item, componentN)
            }
        });
        postVisit(v);
        return nodes;
    }
}
function ex(item, com){
    trampoline(function () {
        return explore(item, com)
    })
}
function trampoline(fn) {
    while(fn && typeof fn === 'function') {
        fn = fn()
    }
}

我想使用setImmediate()以避免堆栈溢出问题（它应该以这种方式实现而不是迭代方式）。但是，当我执行这个函数时，我只得到第一个元素的数组 res ，而如果我不使用 setImmediate() ，我得到它的所有元素，当我使用 nextTick()（我事先知道应该有多少个元素）。我做错了什么，我怎样才能在这里正确地实现这个功能（或模拟）？

这是应用蹦床前的explore()函数

function explore(v, componentN) {
    nodes[v].visited = true;
    nodes[v].componentNumber = componentN;
    preVisit(v);
    adjList[v].forEach((item) => {
        if (!nodes[item].visited){
            explore(item, componentN)
        }
    });
    postVisit(v);
    return nodes;
}

它接受两个参数：v 是 nodes 数组中的索引，应该探索该元素，componentN 只是图中组件的计数器。 explore() 不会 return 任何东西，它只是将 v 键下的数组 nodes 中的对象状态从未探索更改为已探索。主要问题是两个函数 preVisit(v) 和 postVisit(v) 也改变了该对象的状态 - 第一次和第二次访问它的写入顺序（当从以前的调用中弹出堆栈时）分别。当我用 trampoline 转换 explore() 时，他们开始写出意想不到的错误结果。

函数正在另一个函数中以这种方式被调用：

for (let i = 0; i < vNum; i++) {
        if (nodes[i].visited) continue;
        explore(i, cN);
        cN++;
    }

还有两个函数postVisit和preVisit

function preVisit(v){
    nodes[v].preVisit = visitCounter;
    visitCounter++;
}
function postVisit(v) {
    nodes[v].postVisit = visitCounter;
    visitCounter++;
}

Answer 1

假设我们有一个像这样的普通递归函数——这里的问题是我们有一个 forEach 循环，其中对 explore 的每次调用都会产生 0、1 或更多次对 explore – 为了解决这个问题，我们需要一些方法来对所有节点进行排序，这样我们就可以一个接一个地处理它们而不会炸毁堆栈

const explore = node =>
  {
    node.visited = true
    preVisit (node)
    Array.from (node.adjacencies)
      .filter (n => n.visited === false)
      .forEach (n => explore (n))
    postVisit (node)
  }

我们在 explore 函数中引入了一个主循环，它处理数组个节点，而不仅仅是一个节点。当数组中有节点时，循环将继续到运行。将对内部循环函数而不是外部 explore 函数进行递归调用。这种数组方法效果很好，因为每个节点的邻接数量不明确——何时可以轻松地将 0、1 或更多相邻节点添加到此列表——还要注意添加了延续 k，因此我们有一种方法来排序postVisit 调用顺序正确

最重要的是对 loop 的递归调用处于 尾部位置 – 这让我们为下一次转换做好准备

const explore = node =>
  {
    const loop = ([x, ...xs], k) =>
      {
        if (x === undefined)
          k ()
        else {
          x.visited = true
          preVisit (x)
          loop (
            Array.from (x.adjacencies)
              .filter (n => n.visited === false)
              .concat (xs),
            () => (postVisit (x), k ())
          )
        }
      }
    return loop ([node], x => x)
  }

一旦我们有了尾递归循环，我们就可以引入 loop/recur 以实现堆栈安全递归

const recur = (...values) =>
  ({ type: recur, values })

const loop = f =>
  {
    let acc = f ()
    while (acc && acc.type === recur)
      acc = f (...acc.values)
    return acc
  }

const explore = $node =>
  loop (([x,...xs] = [$node], k = x => x) => {
    if (x === undefined)
      return k ()
    else {
      x.visited = true
      preVisit (x)
      return recur (
        Array.from (x.adjacencies)
          .filter (n => n.visited === false)
          .concat (xs),
        () => (postVisit (x), k ())
      )
    }
  })

// for completion's sake
let visitCounter = 0

const preVisit = node =>
  node.preVisit = visitCounter++

const postVisit = node =>
  node.postVisit = visitCounter++

使用 setImmediate() 递归

recursion with setImmediate()

recursion

node.js

setimmediate