Java recursion sum

Question

I need a class Person to describe persons. Each person has a name and an array consisting of Person-objects, which represent the person's children. The person class has a method getNumberOfDescendants, which returns an integer equal to the total number of descendants of the person, i.e. his children plus grandchildren plus their children etc. Is there a simple way to do this using recursion?

What if you want to count the descendants in a certain generation only? In other words, getNumberOfDescendants(int generation) would return the number of children if generation=1, number of grandchildren if generation=2 etc.

Answer 1

Sure.

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 that the "1 +" is the only place where we're actually increasing the count. That line gets called once for every descendant in the tree.

Answer 3

It's not really recursion, per se, but an instance of the class could sum the results of calling the getNumberOfDescendants() method for each of its children.

Alternatively, you could make this method faster by having each instance notify its parent whenever it got a new descendant (either a new child or from being notified by a child). That way, its count of the number of descendants would always be 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;
  }

By the time I wrote the example up, others had posted basically the same thing, so I am kind of redundantly posting.