JS将递归函数转换为trampoline

Question

我正在努力将下面的JS递归函数转换为一个(或多个) trampoline函数，以避免使用深层节点使调用堆栈达到最大。

它返回一个数组，其中包含传入的初始根节点的所有子节点。注意，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;
} 

如何设置trampoline结构，以便构建要在末尾返回的节点数组？

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数组来为下一个执行周期推送子节点ids。在每个节点id上，我们首先检查它是否存在于list映射中。如果是，则将其推送到results中，并迭代其子项，并将其子项ids推送到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中的示例代码