JS将递归函数转换为蹦床

Question

我正在努力将下面的 JS 递归函数转换为蹦床函数，以避免最大化具有深节点的调用堆栈。

它return是从传入的初始根节点开始的所有子节点的数组。注意，list是一个Map，用于下一次递归迭代查找当前节点的子节点。

const getRootSet = (nodeId, list) => {    
  let results = [];
  const node = list.get(nodeId);

  if (node && node.children.size > 0) {       
    results.push(node.nodeId);
    node.children.forEach((value, key) => {
        results = results.concat(getRootSet(list.get(key).nodeId, list) );
    });
  }

  if(node && node.children.size === 0)
  {
    //add last child node
    results.push(node.nodeId);
  }
  return results;
}

如何设置蹦床结构以在最后构建 return 节点数组？

Sample data:
child, parent,
111111, 222222,
000000, 111111,
060270, 964240,
041342, 964240,
024367, 964240,
052643, 964240,
083020, 060270,
024367, 961758,
024367, 964264,
060270, 024367,
060270, 964240,
123456, 789100,
345678, 789100,

Answer 1

我们知道递归使用内存栈来推送和记住下一个递归函数调用，所以我们需要一些东西来记住下一个函数调用。在这里，我使用 nodes 数组为下一个执行周期推送子节点 ID。在每个节点 id 上，我们首先检查它是否存在于 list 映射中。如果是，则将其推入 results 并迭代其子项并将子 ID 推入 nodes 以进行下一个循环。请注意，我正在检查子 ID 是否已被处理以避免循环无限循环。对于当前节点，我使用 index 并且断点是 nodes 的结尾。这是我的解决方案：

const getRootSet = (rootNodeId, list) => {    
   let results = [];
   let nodes = [rootNodeId];
   let index = 0;
   while(index < nodes.length) {
     const node = list.get(nodes[index]);
     if(node) {
       results.push(node.nodeId);
       if (node.children.size > 0) {
         node.children.forEach((val, childId) => {
            if(!nodes.includes(childId)) {
              nodes.push(childId);
            }
         });
       }
     }
     index++;
   }
      
  return results;
};

console.log(getRootSet('root', list));

这是 js 中的示例代码：https://ideone.com/Avnq9h

JS将递归函数转换为蹦床

JS convert recursive function to trampoline

javascript

recursion

trampolines

node.js