python recursion combination

Question

How can I write a function that computes:

C(n,k)= 1                          if k=0
        0                          if n<k
        C(n-1,k-1)+C(n-1,k)     otherwise

So far I have:

def choose(n,k):
if k==0:
   return 1
elif n<k:
   return 0
else:

Answer 1

Assuming the missing operands in your question are subtraction operators (thanks lejlot), this should be the answer:

def choose(n,k):
  if k==0:
     return 1
  elif n<k:
     return 0
  else:
     return choose(n-1, k-1) + choose(n-1, k)

Note that on most Python systems, the max depth or recursion limit is only 1000. After that it will raise an Exception. You may need to get around that by converting this recursive function to an iterative one instead.

Here's an example iterative function that uses a stack to mimic recursion, while avoiding Python's maximum recursion limit:

def choose_iterative(n, k):
  stack = []
  stack.append((n, k))
  combinations = 0

  while len(stack):
    n, k = stack.pop()
    if k == 0:
      combinations += 1
    elif n<k:
      combinations += 0 #or just replace this line with `pass`
    else:
      stack.append((n-1, k))
      stack.append((n-1, k-1))

  return combinations    

Answer 2

Solution from wikipedia (http://en.wikipedia.org/wiki/Binomial_coefficient)

def choose(n, k):
    if k < 0 or k > n:
        return 0
    if k > n - k: # take advantage of symmetry
        k = n - k
    if k == 0 or n <= 1:
        return 1
    return choose(n-1, k) + choose(n-1, k-1)

Answer 3

Improving from Exponential to Linear time

All of the answers given so far run in exponential time O(2n). However, it's possible to make this run in O(k) by changing a single line of code.

---

Explanation:

The reason for the exponential running time is that each recursion separates the problem into overlapping subproblems with this line of code (see Ideone here):

def choose(n, k):
    ...
    return choose(n-1, k-1) + choose(n-1, k)

To see why this is so bad consider the example of choose(500, 2). The numeric value of 500 choose 2 is 500*499/2; however, using the recursion above it takes 250499 recursive calls to compute that. Obviously this is overkill since only 3 operations are needed.

To improve this to linear time all you need to do is choose a different recursion which does not split into two subproblems (there are many on wikipedia).

For example the following recursion is equivalent, but only uses 3 recursive calls to compute choose(500,2) (see Ideone here):

def choose(n,k):
    ...
    return ((n + 1 - k)/k)*choose(n, k-1)

The reason for the improvement is that each recursion has only one subproblem that reduces k by 1 with each call. This means that we are guaranteed that this recursion will only take k + 1 recursions or O(k). That's a vast improvement for changing a single line of code!

If you want to take this a step further, you could take advantage of the symmetry in "n choose k" to ensure that k <= n/2 (see Ideone here):

def choose(n,k):
    ...
    k = k if k <= n/2 else n - k            # if k > n/2 it's equivalent to k - n
    return ((n + 1 - k)/k)*choose(n, k-1)

Answer 4

You're trying to calculate the number of options to choose k out of n elements:

def choose(n,k):
    if k == 0: 
       return 1 # there's only one option to choose zero items out of n
    elif n < k:
       return 0 # there's no way to choose k of n when k > n
    else:
        # The recursion: you can do either
        # 1. choose the n-th element and then the rest k-1 out of n-1
        # 2. or choose all the k elements out of n-1 (not choose the n-th element)
        return choose(n-1, k-1) + choose(n-1, k)

Answer 5

just like this

def choose(n,k):
    if k==0:
        return 1
    elif n<k:
        return 0
    else:
        return choose(n-1,k-1)+choose(n-1,k)

EDIT

It is the easy way, for an efficient one take a look at wikipedia and spencerlyon2 answer