Java再帰合計

Question

個人を説明するクラスPersonが必要です。各人には、名前と、その人の子供を表すPersonオブジェクトで構成される配列があります。 personクラスにはgetNumberOfDescendantsメソッドがあり、これはその人の子孫の合計数に等しい整数を返します。つまり、彼の子供、孫、子供などです。再帰を使用してこれを行う簡単な方法はありますか？

特定の世代の子孫のみをカウントする場合はどうなりますか？つまり、getNumberOfDescendants（int generation）は、generation = 1の場合は子の数を返し、generation = 2の場合は孫の数などを返します。

Answer 1

もちろん。

public class Person {

private Person[] myChildren;

public int getNumberOfDescendants() {
  if (myChildren == null || myChildren.length==0) return 0;
  int myDescendants = 0;
  for (Person child:myChildren) {
    myDescendants += 1; // for this particular child itself
    myDescendants += child.getNumberOfDescendants();  //add the child's children, grandchildren, etc.
  }
  return myDescendants;
}

}

Answer 2

getNumberOfDescendants()
{
  int sum = 0;
  for (int n=0; n < descendants.length; n++)
  {
    sum += 1 + descendants[n].getNumberOfDescendants();
  }
  return sum;
}

＆quot; 1 +＆quot;実際にカウントを増やしている唯一の場所です。その行は、ツリー内の子孫ごとに1回呼び出されます。

Answer 3

それ自体は実際には再帰ではありませんが、クラスのインスタンスは、各子に対してgetNumberOfDescendants（）メソッドを呼び出した結果を合計できます。

別の方法として、新しいインスタンスを取得するたびに（新しい子または子から通知されないように）各インスタンスが親に通知することにより、このメソッドを高速化できます。そうすれば、子孫の数のカウントは常に最新の状態になります。

Answer 4

  public int getNumberDescendents()
  {
    int nDesc = 0;
    if (descendants != null)
    {
      for (Person p : descendants)
      {
        nDesc++; // this child
        nDesc += p.getNumberDescendents(); // this child's desc
      }
    }
    return nDesc;
  }

例を作成するまでに、他の人は基本的に同じことを投稿していたので、私は一種の冗長な投稿をしています。