How do I write a recursive function for a combination

Question

I am going over recursive functions and i understand how to write basic ones, but I have a question on my study guide that I dont understand.

. Write code for a recursive function named Combinations that computes nCr. Assume that nCr can be computed as follows:

nCr = 1 if r = 0 or if r = n and
nCr = (n-1)C(r-1) + (n-1)Cr

Can someone please help me through this or explain in layman's terms? Thank you!

Solution 1

The question really has all the information. It tells you how to compute nCr - and that a lot of the time, you compute it by computing another nCr (with smaller arguments). So your functions might look like this:

int nCr(n, r) {
  if (r == 0 || r == n) return 1;  // stop recursion, we know the answer.
  return nCr(n-1, r-1) + nCr(n-1, r); // the answer is made of the sum of two "easier" ones
}

That's translating as literally as I can. Let's see how that works in practice, by computing

nCr(4,2)
= nCr(4-1, 2-1) + nCr(4-1, 2)
= nCr(3, 1) + nCr(3, 2)
= nCr(3-1, 1) + nCr(3-1,0) + nCr(3-1, 2-1) + nCr(3-1, 2)
= nCr(2, 1) + nCr(2,0) + nCr(2,1) + nCr(2,2)
= nCr(1, 0) + nCr(1,1) + 1 + nCr(1,0) + nCr(1,1) + 1
= 1 + 1 + 1 + 1 + 1 + 1
= 6

Of course we knew that already:

nCr(4,2) = (4 * 3) / (2 * 1) = 6

Solution 2

A recursive function includes calls to itself and a termination case

in your example nCr = 1 if r = 0 or if r = n forms the termination

and (n-1)C(r-1) + (n-1)Cr is the recursion

so your code should look somethink like this

int nCR(int n, int r){
    if (r == 0 || r == n){
        return 1; //terminate
    }
    else{
        return nCr(n-1, r-1) + nCr(n-1, r); //recursive calls
    }
}