Java Rekursion Summe

Question

Ich brauche eine Klasse Person Personen zu beschreiben. Jeder Mensch hat einen Namen und ein Array aus Person-Objekte, die die Person, die Kinder darstellen. Die Person Klasse eine Methode getNumberOfDescendants hat, die eine ganze Zahl gleich die Gesamtzahl der Nachkommen der Person zurückkehrt, das heißt, seine Kinder und Enkelkinder und ihre Kinder usw. Gibt es eine einfache Möglichkeit, diese unter Verwendung von Rekursion zu tun?

Was ist, wenn Sie die Nachfahren in einer bestimmten Generation zählen wollen nur? Mit anderen Worten, würde getNumberOfDescendants (int Generation) gibt die Anzahl der Kinder, wenn Generation = 1, Zahl der Enkelkind, wenn Generation = 2 etc.

Answer 1

Klar.

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

Hinweis

, dass der „1 +“ ist der einzige Ort, wo wir tatsächlich die Zählung zu erhöhen. Diese Zeile einmal für jeden Abkömmling im Baum aufgerufen wird.

Answer 3

Es ist nicht wirklich Rekursion, per se, sondern eine Instanz der Klasse könnte die Ergebnisse des Aufrufs die getNumberOfDescendants () -Methode für jedes seiner Kinder summieren.

Alternativ können Sie diese Methode schneller machen, indem jede Instanz seine Eltern benachrichtigen, die, wenn sie einen neuen Nachkommen (entweder ein neues Kind oder ein Kind zu werden) bekommen. Auf diese Weise, seine Zählung der Anzahl der Nachkommen immer up-to-date sein würde.

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

Als ich das Beispiel schrieb, hatten andere geschrieben im Grunde die gleiche Sache, so dass ich bin ein bisschen redundant veröffentlichen.