Code for finding binomial coefficient in iterative form

Question

I've written the code for finding the binomial coefficient in recursive form:

public int binom(int n, int k)
{
    if (k==n || k==0)
        return 1;
    else return binom(n-1,k-1) + binom(n-1, k);
}

How can I rewrite this code in iterative form instead of recursive form?

Answer 1

public int binom(int n, int k)
    {
        int C[][] = new int[n+1][k+1];
        int i, j;
        int min;

        // Caculate value of Binomial Coefficient in bottom up manner
        for (i = 0; i <= n; i++)
        {
            min = (i<k)? i: k;

            for (j = 0; j <= min; j++)
            {
                // Base Cases
                if (j == 0 || j == i)
                    C[i][j] = 1;

                    // Calculate value using previosly stored values
                else
                    C[i][j] = C[i-1][j-1] + C[i-1][j];
            }
        }

        return C[n][k];
    }

Answer 2

Instead of building the entire Pascal triangle up to the n-th row (memory usage grows quadratically with n), we can simply focus on the row itself, and use constant memory.

Let's find a relationship between consecutive terms on the same row on Pascal's triangle:

Thus we can iteratively generate the terms from ⁿC₀ = 1:

public static int binom(int n, int k)
{
    int value = 1;
    // need to be careful here - can't just use *= due to integer division
    for (int i = 0; i < k; i++)
        value = (value * (n - i)) / (i + 1);
    return value;
}