Java рекурсивная сумма

Question

Мне нужен класс Person, чтобы описать людей. У каждого человека есть имя и массив, состоящий из объектов Person, которые представляют его детей. Класс person имеет метод getNumberOfDescendants, который возвращает целое число, равное общему количеству потомков человека, то есть его детей, внуков, их детей и т. Д. Есть ли простой способ сделать это с помощью рекурсии?

Что если вы хотите считать потомков только в определенном поколении? Другими словами, getNumberOfDescendants (int generation) будет возвращать количество детей, если поколение = 1, количество внуков, если поколение = 2 и т. Д.

Answer 1

Конечно.

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

Обратите внимание, что «1 +» - единственное место, где мы на самом деле увеличиваем количество. Эта строка вызывается один раз для каждого потомка в дереве.

Answer 3

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

К тому времени, когда я написал пример, другие опубликовали в основном то же самое, так что я излишне публикую.

Answer 4

По сути, это не рекурсия, но экземпляр класса может суммировать результаты вызова метода getNumberOfDescendants () для каждого из его дочерних элементов.

В качестве альтернативы, вы могли бы ускорить этот метод, если бы каждый экземпляр уведомлял своего родителя всякий раз, когда он получает нового потомка (либо нового дочернего элемента, либо от уведомления дочерним элементом). Таким образом, счетчик количества потомков всегда будет актуальным.