Two ways of calculating binomial coefficient

binomial_coefficient.ts

// More verbose and integer caching
// O(n^2) first call, best case in subsequent calls: O(1)
let iterations = 0;
const nCr = (n: number, r: number) => {
    if (r == 0 || r == n) {
        return 1;
    }
    nCr[n] = nCr[n] || [];
    if (!nCr[n][r]) {
        nCr[n][r] = nCr(n-1, r-1) + nCr(n-1, r);
        iterations++;
    }
    return nCr[n][r];
};
console.log("Recursive, caching:")
console.log(`50C20 = ${nCr(50, 20)}, iterations: ${iterations}`);
iterations = 0;
console.log(`50C20 = ${nCr(50, 20)}, iterations: ${iterations}`);
iterations = 0;

// Simple non-caching iterative.
// exactly O(r), always 
const nCr2 = (n: number, r: number) => {
    let product = 1;
    for (let i = 1; i <= r; i++) {
        product *= (n + 1 - i) / i;
        iterations++;
    }
    return product;
}

console.log("Iterative, non-caching")
console.log(`50C20 = ${nCr2(50, 20)}, iterations: ${iterations}`);
iterations = 0;
console.log(`50C20 = ${nCr2(50, 20)}, iterations: ${iterations}`);

/*
 * Outputs:
 *
 * Recursive, caching:
 * 50C20 = 47129212243960, iterations: 600
 * 50C20 = 47129212243960, iterations: 0
 * Iterative, non-caching
 * 50C20 = 47129212243960, iterations: 20
 * 50C20 = 47129212243960, iterations: 20
 */