Somma di ricorsione di Java

Question

Ho bisogno di una persona di classe per descrivere le persone. Ogni persona ha un nome e un array costituito da oggetti Person, che rappresentano i figli della persona. La classe persona ha un metodo getNumberOfDescendants, che restituisce un numero intero pari al numero totale di discendenti della persona, ovvero i suoi figli più i nipoti più i loro figli ecc. C'è un modo semplice per farlo usando la ricorsione?

Cosa succede se si desidera contare i discendenti solo in una determinata generazione? In altre parole, getNumberOfDescendants (int generation) restituirebbe il numero di figli se generazione = 1, numero di nipoti se generazione = 2 ecc.

Answer 1

Certo.

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

Nota che " 1 + " è l'unico posto dove stiamo effettivamente aumentando il conteggio. Quella linea viene chiamata una volta per ogni discendente dell'albero.

Answer 3

In realtà non è una vera ricorsione, ma un'istanza della classe potrebbe sommare i risultati della chiamata al metodo getNumberOfDescendants () per ciascuno dei suoi figli.

In alternativa, è possibile rendere più veloce questo metodo facendo in modo che ogni istanza informi il proprio genitore ogni volta che riceve un nuovo discendente (o un nuovo figlio o essere avvisato da un figlio). In questo modo, il suo conteggio del numero di discendenti sarebbe sempre aggiornato.

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

Quando ho scritto l'esempio, altri avevano pubblicato praticamente la stessa cosa, quindi sto scrivendo in modo ridondante.