Recursive function to iterative function as binoms

Question

I'm new with algorithms and wonder how this displayed function is supposed to be converted/transformed from recursive to iterative. What should I keep in mind when converting?

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

    return binom(n - 1, k - 1) + binom(n - 1, k);
}

Thanks in advance!

Answer 1

In fact, this problem is not so easy, if you just look at the recursive code and try to decrypt it. However, it might be a helpful hint for you, that (n over k), i.e. the binomial coefficient can be written as

n! / (k! * (n - k)!)

where "!" denotes the factorial. And it should be rather easy to compute the factorial in a Loop (i.e. iterative) for you.

If intermediate results are too big you can shorten before computation. You can shorten either term k! or the term (n-k)! (you would choose the bigger one). For example with n = 5 and k = 3 you have: (1 * 2 * 3 * 4 * 5) / ((1 * 2 * 3) * (1 * 2)) = (4 * 5) / (1 * 2)

Spoiler-Alarm:

public static int binomial(int n, int k) {
    int nMinusK = n - k;
    if (n < nMinusK) {
        //Switch n and nMinusK
        int temp = n;
        n = nMinusK;
        nMinusK = temp;
    }

    int result = 1;

    //  n!/k!
    for (int i = k + 1; i <= n; i++) {
        result *= i;
    }

    //Division by (n-k)!
    for (int j = 1; j <= nMinusK; j++) {
        result = result / j;
    }
    return result;
}

Answer 2

You can use the multiplicative form of binomial coefficients, for example from Wikia, which can be easily implemented with faculties or loops.