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

java, jsp, recursion, servlets

Solution

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.

Problem

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?

Original source