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

Question

Greetings:

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

I have tried doing this will recursion 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 runs on. Any ideas on best how to do this?

Answer 1

There's means of deep recursion (with risks to get the stack to blow up) if the argument of the method is not immediately resolveable. I.e. 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 causes the code to wait with update() until the result is known and therefore it get kept on the stack. And it accumulates with every method invocation.

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

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

This way the update() can be executed immediately as the argument is immediately resolveable. As long as there's no return value or any other logic to happen after the call to process(), the runtime can optimize it by dropping the call from the stack. Also see the aforelinked wiki article about tail recursion and this website.

However .. The code which you posted seems to be already tail-recursive. So the problem lies somewhere else. After studying your code it look like that you're iterating over the same children everytime. I.e. there's just means of an infinite loop. Probably the if check is bogus and/or the children have backreferences in its own parent-child tree.

Answer 2

I guess you have an infinite loop...

1. childList have the same parent
2. allTremorTransactionsVO is by definition one of the element of childList
3. --> when you recurse, you will again build the same childList and pick the first allTremorTransactionsVO as before

I usually build such recursive code like this:

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

Answer 3

I was running into the same problem recently (using too much stack) and used an iterative algorithm. The example is 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);
   });
}