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 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 function is only defined for n k c n 0 c n n 1 so this is our base case c n k c n n k so if n 2 is sufficiently small we can reduce the problem size else we know c n k n k c n 1 k 1 so we can use this to reduce our problem size
def recursive_binomial_coefficient(n,k):
    

    if k>n:
        raise ValueError('Invalid Inputs, ensure that n >= k')
        
    if k == 0 or n == k:
        
        return 1
    if k > n/2:
        
        return recursive_binomial_coefficient(n,n-k)
    
    return int((n/k)*recursive_binomial_coefficient(n-1,k-1))