The problem with Newton's binomial coefficient in C ++

Question

I have a problem with my program for binocular Newton's coefficients. At first he printed negative numbers, but changing the type of the factorial function to unsigned long long seemed to fix the problem with printing negative numbers. The program works for max n = 20 , printing of zeros, ones, and two begins on it. I don’t know how to fix it, and I hope someone can give me a hand.

 #include <iostream> using namespace std; unsigned long long factorial(int n) { if (n == 0) { return 1; } return n*factorial(n - 1); } void Binom(int n ,int k) { unsigned long long factorialResult; if (k > n) { return; } factorialResult = factorial(n) /(factorial(k) * factorial(n - k)); cout << factorialResult << " "; if (n >= k) { Binom(n, k + 1); } } 

Answer 1

Factorials are usually very large, so you just have integer overflows. To fix this problem, you can implement any other algorithm for computing C(n, k) without using factorials, for example:

 unsigned long long C(unsigned n, unsigned k) { if (n == k || k == 0) { return 1; // There exactly one way to select n or 0 objects out of n } return C(n - 1, k - 1) * n / k; } 

The following repeating rule is used here: C(n, k) = C(n - 1, k - 1) * n / k . This is very easy to prove, since C(n, k) = n! / (k! (nk)!) = (n/k) * (n-1)! / ((k-1)!(n-1-k+1)!) C(n, k) = n! / (k! (nk)!) = (n/k) * (n-1)! / ((k-1)!(n-1-k+1)!) C(n, k) = n! / (k! (nk)!) = (n/k) * (n-1)! / ((k-1)!(n-1-k+1)!) .