組み合わせのコード

Question

return comination(n-1,r-1)+combination(n-1,r)の部分がどのように評価されているかが分かりません。
（combination(4,2)とcomination(4,3)を足すと何になるのだろうか？）
例えばnとrに５と３をいれたときにどのように機能するのでしょうか？教えてください

コード#include <stdio.h>

int combination(int n, int r)
{
    if(n == r) {
        return(1);
    }
    else if(r == 0) {
        return(1);
    }
    else {
        return( combination(n - 1, r - 1) + combination(n - 1, r));
    }
}

int main(void)
{
    int n, r;
    puts("nＣrを求めます。");
    printf("n = "); scanf("%d", &n);
    printf("r = "); scanf("%d", &r);
    
    if (n >= 0 && r >= 0) {
        if(n > r - 1) {
            printf("%dＣ%d = %d\n", n, r, combination(n, r));
        }
    }
    else printf("定義できない数です。\n");
    
    return(0);
}

Answer 1

ロジックは他の方が回答されていますが、パスカルの三角形を紙に書いて
眺めてみるとわかると思います。

再帰のトレースの仕方については、
こんな風にコードにデバッグプリント文を入れてみてください。

int combination(int n, int r)
{
  if(n == r) {
    //printf("combination(%d, %d) = 1\n", n, r);
    return(1);
  }
  else if(r == 0) {
    //printf("combination(%d, %d) = 1\n", n, r);
    return(1);
  }
  else {
    printf("combination(%d, %d) = combination(%d, %d) + combination(%d, %d)\n", n, r, n - 1, r - 1, n - 1, r);
    return( combination(n - 1, r - 1) + combination(n - 1, r));
  }
}

すると、

combination(5, 3) = combination(4, 2) + combination(4, 3)
combination(4, 2) = combination(3, 1) + combination(3, 2)
combination(3, 1) = combination(2, 0) + combination(2, 1)
combination(2, 1) = combination(1, 0) + combination(1, 1)
combination(3, 2) = combination(2, 1) + combination(2, 2)
combination(2, 1) = combination(1, 0) + combination(1, 1)
combination(4, 3) = combination(3, 2) + combination(3, 3)
combination(3, 2) = combination(2, 1) + combination(2, 2)
combination(2, 1) = combination(1, 0) + combination(1, 1)

こんな出力を得ます。
ソースコードから、

combination(1, 0) = 1
combination(1, 1) = 1

であることがわかります。
また、

combination(2, 2) = 1
combination(3, 3) = 1

などであることもすぐにわかると思います。
つまり、

combination(2, 1) = combination(1, 0) + combination(1, 1)

は、

combination(2, 1) = 1 + 1 = 2

です。
このように順番に考えて行くと、次から次へと値が求まっていき、
やがて

combination(5, 3)

にたどり着きます。
このように、再帰しているプログラムをトレースする場合は、
ひたすら処理を追いかけるのではなく、
細切れに分解して逆から計算していくと理解が進むかも知れません。

以下は蛇足です。

デバッグプリント文をよく眺めてみると、
n=5, r= 3 の場合では、

combination(3, 2)

や

combination(2, 1)

など何度も同じ計算をしていることがわかります。

n と r が大きくなればなるほど、このような同じ計算が何度も登場し、
その度に再帰処理をしなければならず、プログラムの処理時間は
次第に遅くなっていきます。

そこで n , r をキーとして答えをハッシュテーブルなどに覚えます。
n, r のキーがハッシュテーブルにあるかを調べ、あったらハッシュテーブルから拾い、
無ければ再帰するようにします。

これを「メモ化」と言います。

このメモ化をすることによって
無駄な計算（再帰処理）を抑えることができ、
処理時間を大幅に短縮することが出来ます。

再帰処理の流れが理解できたら挑戦してみてください。

Answer 2

「パスカルの三角形」の考え方ですね．
nCr,つまりn個からr個取る組み合わせは，n個の中から1個取っておいて，
その1個を含める場合，残りのn-1個からあとr-1個取る組み合わせ(n-1Cr-1)と，
その1個を含めない場合，残りのn-1個からr個取る組み合わせ(n-1Cr)の合計になります．
これをnとrの値を下げていって，n=r(1通りしかない)になるか，r=0(定義より1)になるまで分解していきます．
それを順次足していってもとの組み合わせの数を求めています．

実際の処理の流れを追っていきます．
5C3について書くと長くなるので，3C2で試してみます．
3C2 = 2C1 + 2C2
2C1 = 1C0 + 1C1
1C0 = 1(∵r=0)
1C1 = 1(∵n=r)
よって 2C1 = 1 + 1 = 2
2C2 = 1(∵n=r)
なので 3C2 = 2 + 1 = 3

こうして，3C2の値を求めることができます．

Comments

[reotantan]

ありがとうございます、パスカルの三角形、どこかでやったような。。
とても理解が進みました！