Somme de récursivité Java

Question

J'ai besoin d'une personne de la classe pour décrire les personnes. Chaque personne a un nom et un tableau composé d'objets-personne, qui représentent ses enfants. La classe personne a une méthode getNumberOfDescendants, qui renvoie un entier égal au nombre total de descendants de la personne, c’est-à-dire ses enfants, ses petits-enfants et ses enfants, etc. Existe-t-il un moyen simple de le faire en utilisant la récursivité?

Et si vous voulez compter les descendants d’une génération donnée uniquement? En d'autres termes, getNumberOfDescendants (int generation) renvoie le nombre d'enfants si generation = 1, le nombre de petits-enfants si generation = 2, etc.

Answer 1

Bien sûr.

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

Notez que le " 1 + " est le seul endroit où nous augmentons le nombre. Cette ligne est appelée une fois pour chaque descendant de l’arbre.

Answer 3

Ce n'est pas vraiment une récursion en soi, mais une instance de la classe peut additionner les résultats de l'appel de la méthode getNumberOfDescendants () pour chacun de ses enfants.

Sinon, vous pouvez rendre cette méthode plus rapide en demandant à chaque instance d'avertir son parent chaque fois qu'elle reçoit un nouveau descendant (que ce soit un nouvel enfant ou d'être averti par un enfant). Ainsi, le nombre de ses descendants sera toujours mis à jour.

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

Au moment où j’ai rédigé l’exemple, d’autres avaient déjà publié la même chose, alors je poste en quelque sorte de manière redondante.