Issue with Newton binomial coefficient in c++

Question

I am having an issue with my program for the Newton Binomial Coefficients. At first it printed negative numbers but changing the factorial function type to unsigned long long seemed to have fixed the problem with printing negative numbers. The program works for max n = 20, above it starts printing zeros, ones and twos. No idea how to fix that and hopefully 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

The factorials are typically very large, so you just have an integer overflow here. To fix this issue, you could implement any other algorithm of calculation C(n, k) not using factorials, for example:

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

Here the following recurrent rule is used: C(n, k) = C(n - 1, k - 1) * n / k. It's very easy to prove since C(n, k) = n! / (k! (n-k)!) = (n/k) * (n-1)! / ((k-1)!(n-1-k+1)!).