如何使用递归获得父母的所有孩子，然后是他们的孩子 [英] How to get all children of a parent and then their children using recursion

问题描述

问候：

我在JSP Web应用程序中有父事务的比喻。我将事务ID存储在数据库中，并且要求显示父项的所有子项，然后显示父项子项的后续子项。实际上，这个父母及其子女的名单永远不会超过4或5级，但我需要考虑到它可以比这更多层次。

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?

推荐答案

如果方法的参数不是立即的，那么就会有深度递归（有使堆栈爆炸的风险）的方法resolveable。即被调用方法的最终结果取决于方法本身的结果。伪：

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

这导致代码等待 update（） 直到结果已知，因此它会保留在堆栈中。并且它会在每次方法调用时累积。

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

这样更新（ ）可以立即执行，因为参数可以立即解决。只要在调用 process（）之后没有返回值或任何其他逻辑，运行时就可以通过从堆栈中删除调用来优化它。另请参阅前面提到的有关尾递归的wiki文章以及此网站。

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.

这篇关于如何使用递归获得父母的所有孩子，然后是他们的孩子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！