Pythonで再帰関数を使って組み合わせの計算をする

Pythonのプログラミングで再帰関数を使ったプログラムはたくさん考えられますが、傑作と思われるものを見付けました。それは組み合わせ、つまりn人からr人を選ぶ時の組み合わせを計算するもの（nCr:combination）です。たとえば5人から3人選ぶ場合、$_3C_5=10$と10通りになります。

n人からr人を選び、さらにそのr人のメンバーからリーダーを決める場合の組み合わせを考えると$r\hspace{5px} _n C_r =n$になります。いっぽう、先にn人の中でリーダーを決めて、残ったn-1人からリーダー以外のr-1人のメンバーを選ぶことを考えると、$n\hspace{5px} _{n-1}C_{r-1}$になります。これらの2つは同じことを言っているので等しくなります。そこで次のような公式があります。

$r\hspace{5px} _n C_r =n\hspace{5px} _{n-1}C_{r-1}\hspace{15px}==>\displaystyle_n C_r =\frac{n}{r}\displaystyle _{n-1}C_{r-1}$

def comb(n, r):
    if n == 0 or r == 0: return 1
    return (n / r) * comb(n-1, r-1)      

comb(5,3)

次に、n人からr人を選ぶときに、ある特定の人に注目してその人が選ばれる場合の組み合わせの数と、選ばれない場合の組み合わせの数を合計すればよいわけです。そこで次のような公式があります。

$_nC_r=_{n-1}C_r+_{n-1}C_{r-1}\hspace{15px}(n\geqq1)$

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

アルゴリズムとしては必ずしも効率が良いとは言えませんが、再帰関数の練習としてはとても興味深いものがあります。