soma recursão Java

Question

Eu preciso de uma classe Pessoa para descrever pessoas. Cada pessoa tem um nome e um conjunto constituído por Pessoa-objetos, que representam as crianças da pessoa. A classe pessoa tem um método getNumberOfDescendants, que retorna um inteiro igual ao número total de descendentes da pessoa, ou seja, seus filhos mais netos além de seus filhos etc. Existe uma maneira simples de fazer isso usando recursão?

E se você quiser contar os descendentes em apenas uma certa geração? Em outras palavras, getNumberOfDescendants (geração int) deve retornar o número de crianças se a geração = 1, número de netos se a geração = 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;
}

Note que o "1 +" é o único lugar onde estamos, na verdade, aumentar a contagem. Essa linha é chamado uma vez para cada descendente na árvore.

Answer 3

Não é realmente recursão, per se, mas uma instância da classe pudesse resumir os resultados de chamar os getNumberOfDescendants () para cada um dos seus filhos.

Como alternativa, você pode tornar este método mais rápido por ter cada instância notificar seu pai sempre que ele tem um novo descendente (ou um novo filho ou de ser notificado por uma criança). Dessa forma, a contagem do número de descendentes seria sempre up-to-date.

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

No momento eu escrevi o exemplo acima, outros tinha postado basicamente a mesma coisa, então eu sou tipo de redundância de postar.