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.

This SMELLS like something that should be tagged "homework". — John R. Strohm
– John R. Strohm, Commented Nov 30, 2009 at 19:36
No, no, it's nothing to do with course exercise :D Anyway, I wonder, what the exact difference is between "iteration" and "recursion"? I think it's recursion, when you call a method inside itself, like in the sample solutions, but iteration is "for, while" etc.? I guess there is no purely recursive solution? That is, a solution, which does not use the for-loop? — rize
– rize, Commented Nov 30, 2009 at 20:02
Many solutions that are termed recursive have some element of iteration; for example, think about the algorithms to traverse a binary tree -- typically the recursive function calls itself on the left node and then on the right node; this is, in a sense, an iteration of the list of (two) nodes. Recursion is a useful way to get information from a lower level to an upper level, but to get information across a given level (e.g. summarize all of the children of the current node) you'll want to iterate. — Jacob Mattison
– Jacob Mattison, Commented Nov 30, 2009 at 20:37

Jacob Mattison · Accepted Answer · 2009-12-02 14:26:06Z

4

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

}

edited Dec 2, 2009 at 14:26

answered Nov 30, 2009 at 19:34

Jacob Mattison

51.2k11 gold badges109 silver badges128 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Jacob Mattison Over a year ago

Note that the two lines that do the incrementing could easily be replaced with a single line "myChildren += 1 + child.getNumberOfDescendants();". I did it as two lines for clarity and ease of commenting.

rize Over a year ago

Yes, that's the way I finally wrote it. Anyway, thanks for example, now I got the hang of recursion in this.

Jacob Mattison Over a year ago

Fixed a small problem (hadn't specified the return type). Compiles now.

Nate C-K · Accepted Answer · 2009-11-30 19:33:41Z

4

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.

answered Nov 30, 2009 at 19:33

Nate C-K

5,9812 gold badges32 silver badges46 bronze badges

5 Comments

Jacob Mattison Over a year ago

Only problem here is the assumption the descendants array will never be null.

Nate C-K Over a year ago

True... I guess I was thinking in terms of collections where even an empty one will still usually have an object allocated that you can traverse (0 times). Does Java allow 0-length arrays?

Jacob Mattison Over a year ago

Yes, the array can exist but have a zero length, in which case your code will work.

D'Nabre Over a year ago

If the descendants array is null, it's .length will be 0, and the loop won't be entered.

Jacob Mattison Over a year ago

D'Nabre: No, if the array is initialized but has no members, it's .length will be 0, but if it's null, calling .length on it will cause a null pointer exception.

Steve Emmerson · Accepted Answer · 2009-11-30 19:37:37Z

0

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.

answered Nov 30, 2009 at 19:37

Steve Emmerson

7,8426 gold badges36 silver badges59 bronze badges

Comments

Jacob Mattison · Accepted Answer · 2009-11-30 20:37:42Z

0

  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.

edited Nov 30, 2009 at 20:37

Jacob Mattison

51.2k11 gold badges109 silver badges128 bronze badges

answered Nov 30, 2009 at 19:56

PaulP1975

5281 gold badge5 silver badges12 bronze badges

1 Comment

Nate C-K Over a year ago

If you put 4 spaces at the beginning of each line, it will put the code in a nice formatted code block.

Collectives™ on Stack Overflow

Java recursion sum

4 Answers 4

3 Comments

5 Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

5 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related