### Compute binomial coefficient recursion binomial dynamicprogramming    Posted: 5 years ago Edit answers (1) views (2339)

Write a recursive function to compute the binomial coefficient $$C(n,k)$$ of given two parameters $$n$$ and $$k$$.

 Posted: 5 years ago Updated: 5 years ago 0 0 Edit The binomial coefficient $$C(n,k)$$ can be recursively computed as $$C(n,k) = C(n-1,k-1)+C(n-1,k)$$, $$C(n,0) = C(n,n)=1$$int CompBinomialCoefficient(int n, int k){ /* Base case */ if(k == 0 || k == n) return 1; else return CompBinomialCoefficient(n-1,k-1) + CompBinomialCoefficient(n-1,k); }Since some sub problems are called more than once, we can use dynamic programming. Re-computation of same problem can be avoided by constructing a temporary $$2d$$ array in $$bottom$$ - $$up$$ manner.int CompBinomialCoefficient(int n, int k){ int C[n+1][k+1]; for(int i = 0; i < = n; i++){ for(int j = 0; j < = min(i,k); j++){ /* Base case */ if(j == 0 || j == i) C[i][j] = 1; else C[i][j] = C[i-1][j-1] + C[i-1][j]; } } return C[n][k]; }Time complexity = $$O(nk)$$.