0

我有以下递归函数：

 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()不返回任何内容，它只是nodes将键下数组中对象的状态v从未探索更改为已探索。主要问题是这两个函数preVisit(v)还postVisit(v)改变了该对象的状态 - 分别写入第一次和第二次访问它的顺序（从先前的调用弹出堆栈时）。当我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++;
}
4

1 回答 1

0

假设我们有一个像这样的普通递归函数——这里的问题是我们有一个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++
于 2017-10-27T23:49:24.933 回答