Как получить всех детей от родителей, а затем их детей с помощью рекурсии

Question

Приветствия:

У меня есть метафора родительских транзакций в моем веб-приложении JSP. У меня есть идентификаторы транзакций, хранящиеся в базе данных, и требование состоит в том, чтобы отобразить все дочерние элементы родителя, а затем последующих дочерних элементов родителя. На самом деле этот список родителей и их детей никогда не будет иметь глубину более 4 или 5 уровней, но я должен принять во внимание, что он может иметь больше уровней, чем этот.

Я попытался выполнить эту рекурсию следующим образом:

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;
}

Это не работает, генерирует переполнение стека при запуске цикла. Есть идеи, как лучше всего это сделать?

Answer 1

Существуют средства глубокой рекурсии (с риском взорвать стек), если аргумент метода не может быть сразу разрешен. То есть конечный результат вызванного метода зависит от результата самого метода. Псевдо:

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

Это заставляет код ждать с update(), пока результат не станет известен, и, следовательно, он останется в стеке. И он накапливается при каждом вызове метода.

Вы можете оптимизировать его для использования хвостовой рекурсии вместо этого с изменяемым объектом результата в качестве аргумента:

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

Таким образом, update() может быть выполнен немедленно, так как аргумент сразу разрешается. Если после вызова process() не существует возвращаемого значения или какой-либо другой логики, среда выполнения может оптимизировать его, отбрасывая вызов из стека. Также смотрите вышеупомянутую статью вики о хвостовой рекурсии и этот сайт .

Однако .. Код, который вы разместили, кажется, уже хвост рекурсивным. Так что проблема кроется где-то еще. После изучения вашего кода, похоже, вы каждый раз перебираете одинаковых детей. То есть есть просто средство бесконечного цикла. Вероятно, проверка if является фиктивной, и / или дочерние элементы имеют обратные ссылки в своем собственном родительско-дочернем дереве.

Answer 2

Я думаю, у вас есть бесконечный цикл ...

1. childList имеют одного и того же родителя
2. allTremorTransactionsVO по определению является одним из элементов childList
3. -> когда вы вернетесь, вы снова построите тот же childList и выберете первый allTremorTransactionsVO, как и раньше

Обычно я создаю такой рекурсивный код, подобный этому:

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

Answer 3

Недавно я столкнулся с той же проблемой (используя слишком много стека) и использовал итерационный алгоритм. Пример написан на Javascript, но может быть легко адаптирован:

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

Мне удалось решить мое условие StackOverflow следующим образом:

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;

}

У меня теперь есть все дети, но я изо всех сил пытаюсь сгруппировать их должным образом. Их нужно перечислить так:

Родитель --Child / Родитель ---- Детский родитель --Child / Парнет ---- Ребенок / Родитель ------ Детский

и т. Д.

Answer 5

Если происходит переполнение стека, ваша рекурсия выполняется слишком глубоко. Вам придется переписать алгоритм как итеративную конструкцию (т.е. с использованием цикла for / while / foreach).