CODEWITHSUNDEEP
javarecursion
Barry
Barry

Reputation: 1665

Returning a value early from a recursive function

I have a tree of nodes. While iterating this tree depth first, I need to return the list of all duplicate nodes from the root node to my current node.

Due to some business requirements the "already traversed" part of the tree is never the same. I do a lot of swap/replaces of branches in the already traversed part of the tree. So maintaining a list of traversed nodes might not work as it needs updates every time I finish traversing a node.

So whenever I need to answer getDuplicateNodesOfMyCurrentNode() I need to start from the top of the tree (rootNode) and search depth-first till my currentNode and return back a list<Nodes> that are duplicates of my currentNode.

private void getDuplicateNodesOfMyCurrentNode(Node parentNode, Node currentNode,List<Node> dupNodes){
  for(Node child: parentNode.getChildren()){
        if(child == currentNode){
            return;
        }
        if(child.getApp().equals(currentNode.getApp()){
            dupNodes.add(child);
        }
        getDuplicateNodesOfMyCurrentNode( child, currentNode, aDupNodes);

}

As you guys already know the issue with this code, return doesn't return back the control to the caller of this API since it recursively calls itself. I want some way to exit out of this recursive loop once I get to my currentNode.

I probably can achieve this by maintaining some boolean state, but want to know the better way of solving this.

Upvotes: 0

Views: 789

Answers (1)

VirtualMichael
VirtualMichael

Reputation: 721

Pass whether or not to abort your recursion back through the call stack via a boolean and abandon the current for loop if necessary at the point of the recursive call (also acknowledging Norbet van Nobelen's comment above that alludes to something similar):

private boolean getDuplicateNodesOfMyCurrentNode(Node parentNode, Node currentNode,List<Node> dupNodes){
    for(Node child: parentNode.getChildren()){
        if(child == currentNode){
            return false;
        }
        if(child.getApp().equals(currentNode.getApp()){
            dupNodes.add(child);
        }
        if (getDuplicateNodesOfMyCurrentNode( builtOn, currentNode, aDupNodes) == false){
            return false;
        }
    }
    return true;
}

Upvotes: 2

Related Questions