how to boost Combination recursive function's performance?

Question

compute combination is as follows:

def C(n,r):
    if n==r:
        return 1
    elif r==1:
        return n
    else:
        return C(n-1,r)+C(n-1,r-1)

While refer the above equation to compute C( 990, 33 ), python will take too much time.

how to boost its performance??

From the linked question, `def C(n, r): return scipy.special.comb(n, r, exact=True)`, or better yet in Python 3.8, `C = math.comb` — Eric, Dec 04 '19 at 13:18
From another answer there [here's how to implement the cache mentioned above](https://stackoverflow.com/a/51640070/102441) — Eric, Dec 04 '19 at 13:24

score 0 · Accepted Answer · answered Dec 04 '19 at 13:18

Inspired by the comment by @user1558604; this is a lot quicker:

cache = dict()

def C(n,r):
    if (n,r) in cache:
        return cache[(n,r)]
    elif n==r:
        cache[(n,r)] = 1
        return 1
    elif r==1:
        cache[(n,r)] = n
        return n
    else:
        cache[(n,r)] = C(n-1,r)+C(n-1,r-1)
        return C(n-1,r)+C(n-1,r-1)

Output:

>>> import timeit
>>> %timeit C(990, 33)
321 ns ± 24.7 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Is this method able to use Tail Recursion to optimize ?? – willy chang Dec 04 '19 at 13:27 — willy chang, Dec 04 '19 at 13:27

how to boost Combination recursive function's performance?

1 Answers1