title: Recursion to get the number of different combinations of n people and k groups
body: <p>I'm practicing recursion using Java and I've hit a problem. I'm trying to make a method which I'm calling "groups" which takes a number of people and how many groups there are and returns the number of different combinations there are of people and groups. Also, the ordering of people in the groups does not matter, nor does the ordering of the groups.</p>
  
  <p>The code I have so far is:</p>
  
  <pre><code>public long groups(int n, int k) {
      if(k==1) return 1;
      if(k==n) return 1;
      else return groups(n-1, k) + groups(n-1, k-1);
  }
  </code></pre>
  
  <p>However it returns the wrong values. The first two lines are the base cases, which say if there is 1 group, then there is only one way to split the people up, makes sense. The other is when there are just as many people as there are groups, in which case theres only one way to split them up, one person into each group. The last statement is where I think I'm having problems, I would think that each time it does a recursive call, one person has to be taken out (n is the number of people, so n-1) and that person can ether join a group (k) or make their own group (k-1).</p>
  
  <p>I'm just having a little trouble figuring out how recursion works and could use a little help.</p>
  
  <p>These are the values I'm expecting:</p>
  
  <pre><code>groups(2,1) = 1
  groups(2,2) = 1
  groups(3,2) = 3
  groups(4,2) = 7
  groups(4,3) = 6
  groups(5,3) = 25
  </code></pre>