用setImmediate()进行递归
我有以下递归函数：
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++;
}回答 1
Stack Overflow用户
发布于 2017-10-27 23:49:24
假设我们有一个像这样的普通递归函数--这里的问题是，我们有一个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++https://stackoverflow.com/questions/46753241
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号