Suma de recursión de Java

Question

Necesito una clase Persona para describir personas. Cada persona tiene un nombre y una matriz que consiste en objetos Persona, que representan a los hijos de la persona. La clase de persona tiene un método getNumberOfDescendants, que devuelve un número entero igual al número total de descendientes de la persona, es decir, sus hijos más nietos más sus hijos, etc. ¿Hay una manera simple de hacer esto usando la recursión?

¿Qué sucede si desea contar los descendientes solo en una determinada generación? En otras palabras, getNumberOfDescendants (int generation) devolvería el número de hijos si generation = 1, número de nietos si generation = 2, etc.

Answer 1

Claro.

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

Tenga en cuenta que " 1 + " es el único lugar donde en realidad estamos aumentando la cuenta. Esa línea se llama una vez por cada descendiente en el árbol.

Answer 3

No es realmente una recursión, per se, pero una instancia de la clase podría sumar los resultados de llamar al método getNumberOfDescendants () para cada uno de sus hijos.

Alternativamente, puede hacer que este método sea más rápido haciendo que cada instancia notifique a su padre cada vez que tenga un nuevo descendiente (ya sea un nuevo hijo o un niño). De esa manera, su recuento del número de descendientes siempre estaría actualizado.

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

Cuando escribí el ejemplo, otros habían publicado básicamente lo mismo, así que estoy publicando de forma redundante.