How to get all the children of a parent and then their children using recursion

Question

Greetings:

I have a parent transaction metaphor in my JSP web application. I have a transaction identifier stored in a database, and the requirement is to display all the children of the parent and then the subsequent descendants of the parent children. In fact, this list of parents and their children will never be more than 4 or 5 levels, but I need to take into account that it can go more layers than this.

I tried to do this, recursion is as follows:

private static void processChildrenTransactions( AllTremorTransactionsVO parentBean, ArrayList<AllTremorTransactionsVO> childCandidatesList ) { ArrayList<AllTremorTransactionsVO> childList = new ArrayList<AllTremorTransactionsVO>(); for (AllTremorTransactionsVO childTransactions : childCandidatesList) { if (childTransactions.getParentGuid() != null) { if (childTransactions.getParentGuid().equals(parentBean.getTransactionGuid())) { childList.add(childTransactions); } } } for (AllTremorTransactionsVO allTremorTransactionsVO : childList) { processChildrenTransactions(allTremorTransactionsVO, childList); } return; } 

This does not work, generates a stack overflow as the loop starts. Any ideas on how to do this?

Answer 1

There is a deep recursion tool (with risks for the stack to explode) if the method argument cannot be resolved immediately. That is, the final result of the called method depends on the result of the method itself. Pseudo:

 Result process(Parent parent) { Result result = new Result(); for (Child child : parent.getChildren()) { result.update(process(child)); } return result; } 

This makes the code wait with update() until the result is known, and therefore it will be stored on the stack. And it accumulates with every method call.

You can optimize it to use tail recursion instead with a mutable result object as an argument:

 void process(Parent parent, Result result) { for (Child child : parent.getChildren()) { result.update(child); process(child, result); } } 

Thus, update() can be executed immediately, since the argument can be resolved immediately. As long as there is no return or any other logic after calling process() , the runtime can optimize it by dropping the call from the stack. Also see Article a wap-wiki on tail recursion and this website .

However .. The code you posted seems to be tail-recursive already. So the problem lies elsewhere. Having studied your code, you look as if you are repeating all the same children every time. That is, it is simply a means of an endless cycle. The if check is probably fictitious and / or children have backlinks in their own parent tree.

Answer 2

I think you have an infinite loop ...

• childList have the same parent
• allTremorTransactionsVO by definition one of the elements of a childList
• → when you recurs, you will again create the same childList and select the first allTremorTransactionsVO as before

I usually create such recursive code as follows:

 public List allChildren( Transaction trans ) { List allChildren = new List(); for( Transaction childTrans : trans.getChildren() ) { allChildren.addAll( allChildren( childTrans )); } return allChildren; } 

Answer 3

Recently, I ran into the same problem (using too many stacks) and used an iterative algorithm. An example is provided in Javascript, but can be easily adapted:

 var nodeStack = new Array(); nodeStack.push(root); while(nodeStack.length > 0) { var currentNode = nodeStack.pop(); var data = currentNode.data; var children = currentNode.children; /* do stuff with data */ if(children.length > 0) { jQuery.each(children, function(index, value) { nodeStack.push(value); }); } 

Answer 4

If a stack overflow occurs, your recursion is too deep. You will have to rewrite the algorithm as iterative (i.e. use the for / while / foreach construct).

Answer 5

I was able to solve my StackOverflow state as follows:

 private static void processChildrenTransactions(AllTremorTransactionsVO parentBean, ArrayList<AllTremorTransactionsVO> childCandidatesList ) { ArrayList<AllTremorTransactionsVO> childList = new ArrayList<AllTremorTransactionsVO>(); ArrayList<AllTremorTransactionsVO> childListTwo = new ArrayList<AllTremorTransactionsVO>(); for (AllTremorTransactionsVO childTransactions : childCandidatesList) { childListTwo.add(childTransactions); if (childTransactions.getParentGuid() != null) { //gets a list of every trans with a child if (childTransactions.getParentGuid().equalsIgnoreCase(parentBean.getTransactionGuid())){ childList.add(childTransactions); childListTwo.remove(childTransactions); } } } parentBean.setChildTransactions(childList); for (AllTremorTransactionsVO allTremorTransactionsVO : childList) { processChildrenTransactions(allTremorTransactionsVO, childListTwo); //processChildrenTransactions(allTremorTransactionsVO, childList); } return; } 

Now I have all the children, but I struggle with their correct grouping. They should be listed as follows:

Parent --Child / Parent ---- Child Parent --Child / Parnet ---- Child / Parent ------ Child

Etc.