Сумма рекурсии Java

Question

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

Что делать, если вы хотите подсчитать потомков только в определенном поколении?Другими словами, 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

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

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

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

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