javascriptnode.jsrecursiontrampolines

JS convert recursive function to trampoline


I am struggling to convert the JS recursive function below into a a trampoline function(s) in order to avoid maxing out the call stack with deep nodes.

It returns an array of all children nodes from the initial root node passed in. Note, list is a Map used to lookup the children of the current node for the next recursion iteration.

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;
} 

How do I setup the trampoline structure in order to build the array of nodes to return at the end?

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,

Solution

  • As we know that recursion uses memory stack to push and remember the next recursive function calls, so we need something to remember our next function calls. Here I'm using nodes array to push child node ids for next execution cycle. On each node id first we check if it exists in the list map. If yes then push it into results and iterate its children and push child ids in nodes for next cycle. Note that I'm checking if a child id has already been processed or not to avoid a cyclic infinite loop. And for the current node I'm using index and the break point is the end of nodes. Here's my solution:

    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));
    

    Here's the sample code in js: https://ideone.com/Avnq9h