再帰の使い方について

Question

###前提
c言語を書籍で勉強している学生です。
書籍には回答がないため、質問する回数が多くなりがちです。

###問題
異なるn個の整数からr個の整数を取り出す組み合わせの数n C rを求める関数を作成せよ。

int combination (int n, int r) {/* ... */}

なおn C r は以下のように定義される。
n C r = n-1 C r-1 + n-1 C r (ただし、n C 0 = n C n = 1, n C 1 = n)

###該当のソースコード

/*階乗値を求める */
int factorial (int n)
{
    if(n < 0){
        return n * factorial(n - 1);
    }else {
        return 1;
    }
}

/*組み合わせを求める*/
int combination (int n, int r)
{
    return factorial(n) / factorial(r) / factorial(n - r);
}

###疑問点
再帰を使うのは分かるのですが、どのように使えばいいのか分かりません。
n C r = n! / r!(n - r)! という性質を使って上記のコードを作成したのですが、上手く動作しませんでした。

###補足情報
書籍 ： 新明解c言語 入門編
演習８－７

Answer 1

なおn C r は以下のように定義される。

n C r = n-1 C r-1 + n-1 C r (ただし、n C 0 = n C n = 1, n C 1 = n)

すっげーヒントが書いてあるやん。これを忠実に実装すればいい。

#include <stdio.h>

int combination(int n, int r) {

  /* nC0 = nCn = 1 */ 
  if ( r == 0 || n == r ) return 1; 

  /* nC1 = n */ 
  if ( r == 1 ) return n; 

  /* n-1Cr-1 + n-1Cr */
  return combination(n-1, r-1) + combination(n-1, r); 
}

int main() {
  int n, r;
  for ( n = 1; n < 6; ++n ) {
    for ( r = 0; r <= n; ++r ) {
      printf("C(%d,%d) = %d\n", n, r, combination(n,r));
    }
    printf("\n");
  }
  return 0;
}

Comments

[kamecha]

有り難うございます。
なるほど、その様にすればいいのですね。
頑張って理解します！

Answer 2

理論上はn!/(r!(n-r)!)でも実装できますが、C言語ではintの限界が早々に来てしまうので、狙ったとおりには動かなくなります（Rubyのように、整数の桁数が無限に入る環境なら、これでも動きます）。

…というより、

なおn C r は以下のように定義される。

n C r = n-1 C r-1 + n-1 C r (ただし、n C 0 = n C n = 1, n C 1 = n)

と書いてある以上、こちらに従って実装するのが題意ではないかと思うのですが。

Comments

[kamecha]

その通りなのですが、どうしても実装の仕方が分からなかったので、その段階で分かっていた階乗値を使って何とか動くプログラムを作ろうとした結果このようになってしまいました…

[maisumakun]

再帰を使った階乗の実装が（いくつか問題があるけど）できているのに、再帰的に定義が書かれているnCrのほうが「どうしてもわからない」というのが、よくわからなかったです。

[kamecha]

高校１年生の頃
n C r は n! / r! / (n - r)!と計算していたため、
n C r = n-1 C r-1 + n-1 C r という定義式がどの様な計算をしているか、よく分からなかった為です。
（高1の頃、理解できていれば…）

[maisumakun]

「パスカルの三角形」で調べてみてください。

[kamecha]

有り難うございます。
この分野は苦手だった為、復習もかねて理解していこうと思います。

Answer 3

効率的な方法は他者の回答を参考にしてください。本質はおそらくここです。不等号よくみて！

if(n < 0)

Comments

[kamecha]

有り難うございます。
if (n > 0)に変更すると上手く動作してくれました。
これで取り合えず動くプログラムは作れました！