java - 如何使用递归获取 parent 的所有 child ，然后是他们的 child

Question

问候:

我的 JSP 网络应用程序中有父事务的比喻。我将事务 ID 存储在数据库中，要求显示父项的所有子项，然后显示父项的子项的后续子项。实际上，这个 parent 和他们的 child 的列表永远不会超过 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

如果方法的参数不能立即解析，则可以使用深度递归(存在堆栈崩溃的风险)。 IE。被调用方法的最终结果取决于方法本身的结果。伪:

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

这导致代码等待 update() 直到结果已知，因此它被保存在堆栈中。它随着每次方法调用而累积。

您可以优化它以使用 tail recursion取而代之的是一个可变的结果对象作为参数:

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

这样 update() 可以立即执行，因为参数可以立即解析。只要在调用 process() 之后没有返回值或任何其他逻辑发生，运行时就可以通过从堆栈中删除调用来优化它。另请参阅前面关于尾递归和 this website 的维基文章。 .

但是 .. 您发布的代码似乎已经是尾递归的。所以问题出在其他地方。在研究了您的代码之后，您似乎每次都在对相同 子项进行迭代。 IE。只有无限循环的方法。可能 if 检查是伪造的和/或 child 在其自己的父子树中有反向引用。