CODEWITHSUNDEEP
cbinomial-coefficients
Rick
Rick

Reputation: 89

Binomial Coefficient in C program explanation

So I have to write a program that prints out the eleven 10th order binomial coefficients. I came across this code that does what I needed, but I'm trying to understand why it works.

    #include<stdio.h>

int binomialCoeff(int n, int k)
{
    if(k == 0)return 1;
    if(n <= k) return 0;

    return (n*binomialCoeff(n-1,k-1))/k;
}

int main()
{
    int k;
    for(k=10;k>=0;k-=1)
    {
          printf("%d\n", binomialCoeff(10, k));
    }

I get why the int main part works, I just don't get how the binomialCoeff calculation is made. I'm relatively new to all of this coding stuff, so thank you for the help!

Upvotes: 5

Views: 5371

Answers (1)

Cripto
Cripto

Reputation: 3751

This is actually pretty elegant.

The function binomialCoeff is a recursive function with 2 base conditions. If k == 0, you return just 1. If n<k you return 0. So if none of that is true, you recall the same function by subtracting one from n and k. This repeats resulting in

n * (binomialCoeff(n-1,k-1))/k

So say N is 10 and K is 7

you get

 10*(binomialCoeff(9,6)/7)

Just to keep things simple, lets call the first time binomialCoeff is called res1. Which simplifies things to:

10*(res1/6)

but res1 itself calls binomialCoeff

resulting in

 9*(binomialCoeff(8,5)/6)

which we can call res2

so we get

10*(res2/6)

and so on until you meet the base conditions; resulting in a series of n's multiplied together.

Upvotes: 5

Related Questions