Calculate value of n choose k

Here is my version, which works purely in integers (the division by k always produces an integer quotient) and is fast at O(k):

function choose(n, k)
    if k == 0 return 1
    return (n * choose(n - 1, k - 1)) / k

I wrote it recursively because it's so simple and pretty, but you could transform it to an iterative solution if you like.

You could use the Multiplicative formula for this:

enter image description here

http://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula

Related