Calculates the binomial coefficient, Cn,k, with nk using recursion Time complexity is Ok, so can calculate fairly quickly for large values of k.  recursivebinomialcoefficient5,0 1  recursivebinomialcoefficient8,2 28  recursivebinomialcoefficient500,300 5054949849935535817667719165973249533761635252733275327088189563256013971725761702359997954491403585396607971745777019273390505201262259748208640 function is only defined for nk Cn,0  Cn,n  1, so this is our base case. Cn,k  Cn,nk, so if n2 is sufficiently small, we can reduce the problem size. else, we know Cn,k  nkCn1,k1, so we can use this to reduce our problem size.
def recursive_binomial_coefficient(n,k):
    """Calculates the binomial coefficient, C(n,k), with n>=k using recursion
    Time complexity is O(k), so can calculate fairly quickly for large values of k.

    >>> recursive_binomial_coefficient(5,0)
    1

    >>> recursive_binomial_coefficient(8,2)
    28

    >>> recursive_binomial_coefficient(500,300)
    5054949849935535817667719165973249533761635252733275327088189563256013971725761702359997954491403585396607971745777019273390505201262259748208640

    """

    if k>n:
        raise ValueError('Invalid Inputs, ensure that n >= k')
        #function is only defined for n>=k
    if k == 0 or n == k:
        #C(n,0) = C(n,n) = 1, so this is our base case.
        return 1
    if k > n/2:
        #C(n,k) = C(n,n-k), so if n/2 is sufficiently small, we can reduce the problem size.
        return recursive_binomial_coefficient(n,n-k)
    #else, we know C(n,k) = (n/k)C(n-1,k-1), so we can use this to reduce our problem size.
    return int((n/k)*recursive_binomial_coefficient(n-1,k-1))
