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!
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.