How can I make my recursvie n choose k function work with big numbers in Python?

Question

The title says it all, my function isn't working with big numbers. For example (1000 C 800) would crash it.

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

Any recursive solution can be made an iterative method by using a data-structure to store previous results. As for the answer to your question this is a duplicate of https://stackoverflow.com/questions/15301885/calculate-value-of-n-choose-k — Prateek, Oct 07 '17 at 19:01
Do not use recursion, neither iteration. A closed form solution exists. — wim, Oct 07 '17 at 19:02

score 0 · Answer 1 · answered Oct 07 '17 at 19:11

def choose(n, k):
  dp = [[0 for x in xrange(k+1)] for x in xrange(n+1)]

  for i in xrange(n+1):
    for j in xrange(k+1):
      if j > i:
        continue
      if j == 0:
        dp[i][j] = 1
      elif j == i:
        dp[i][j] = 1
      else:
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

  return dp[n][k]

You could use dynamic programming to avoid calculating the same subproblems over and over again. It comes at the cost of some space.

trincot · Answer 2 · 2017-10-07T20:13:14.617

To avoid repeated recalculation of the same sub result, you could use a bottom-up, iterative solution, building a row of Pascal's triangle, and then the next one from it, ...etc:

def choose(n, k):
    lst = [1] * (n+1)
    for j in range(1, n):
        for i in range(j, 0, -1):
            lst[i] += lst[i-1]
    return lst[k]

print(choose(1000, 800))

661715556065930365627163346132458831897321703017638669364788134708891795956726411057801285583913163781806953211915554723373931451847059830252175887712457307547649354135460619296383882957897161889636280577155889117185

This is just to show how to make the approach more efficient, but there are of course several more efficient ways to calculate C(n,k).

score 0 · Answer 3 · answered Oct 07 '17 at 19:28

You can make the recursive approach perform a lot better by dividing through factors:

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

This uses the recurrence relation:

This approach will instantly compute 1000 C 800 without blowing the recursion stack. But, the underlying problem is still there - it's just postponed to much larger numbers. You may prefer to use one of the various closed-form solutions instead, for example:

from math import factorial

def choose(n, k):
    if n < k:
        n = k - n
    return factorial(n) // (factorial(k) * factorial(n-k))

How can I make my recursvie n choose k function work with big numbers in Python?

3 Answers3