如何使用递归获得父母的所有孩子,然后是他们的孩子

Question

问候:

我在JSP Web应用程序中有父事务的比喻.我将事务ID存储在数据库中,并且要求显示父项的所有子项,然后显示父项子项的后续子项.实际上,这个父母及其子女的名单将永远不会超过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(),运行时就可以通过从堆栈中删除调用来优化它.另请参阅前面提到的有关尾递归和本网站的 wiki文章.

但是..你发布的代码似乎已经是尾递归的.所以问题出在其他地方.在研究了你的代码之后,你看起来每次都在迭代同一个孩子.也就是说,只有无限循环的手段.可能if检查是伪造的和/或孩子们在其自己的亲子树中有反向引用.