algorithm - Calculate value of n choose k

Question

What is the most efficient method to evaluate the value of n choose k ? The brute force way I think would be to find n factorial / k factorial / (n-k) factorial .

A better strategy may be to use dp according to this recursive formula. Is there any other better method to evaluate n choose k ?

Answer 1

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.