Stop this recursive call once all the items in the items(array) is visited (JavaScript)

user_6359303 0
Viewed 72

I am trying to make a recursion call of this.isParentEmpty() inside this method and I need to stop this recursion once all the items are visited . Maybe using a counter.. Here for example I have items.length as 3 then the recursion should only happen till the time the length is met and break after that in order to avoid infinite loop or circular dependencies.. What could be the stopping condition for this??

isParentEmpty(item, items) {
  const parentSystemRecordId = R.path(['parent', 'id'], item);
  
  if(!parentSystemRecordId || !item.isDependentList) {
    return false;
  }
  
  const parentItem = 
    items.find(({ _id }) => Number(_id) === parentSystemRecordId);
          
  if(this.isParentEmpty(parentItem, items)) {
    return true;
  }
          
  return parentItem && !R.path(['value', 'id'], parentItem);
}
infinite-recursion break recursion arrays javascript
1 Answers

You can pass a Set along in your function that marks which items you have visited.

To check whether you should process an item, you can check your set with visited.has(item).

Not sure about your specific example, but here's a more generic proof of concept:

const nodeA = { id: "A", links: [] };
const nodeB = { id: "B", links: [] };
const nodeC = { id: "C", links: [] };
const nodeD = { id: "D", links: [] };

// Create a circular structure
nodeA.links.push(nodeB);
nodeB.links.push(nodeC);
nodeC.links.push(nodeC);
nodeB.links.push(nodeD);
nodeD.links.push(nodeA);

// Write a recursive function that will only visit each node once
const visitOnce = (node, f, visited = new Set(), distance = 0) => {
  // Mark the node as visited
  visited.add(node);
  
  // Execute some logic / side effect
  f(node, distance);
  
  node.links
    // Prevent recursion for nodes that have been visited
    .filter(n => !visited.has(n))
    // Recurse, pass the set along
    .forEach(n => visitOnce(n, f, visited, distance + 1));
}


visitOnce(nodeA, (n, d) => console.log(`${n.id} at distance ${d}`));

user_32972910
Related