再帰関数の宿題

[羽流布]

（問題）
組合せの総数（二項係数）nCr は次の関係式で定義できる．
　nC0 = 1 (n >= 0)
　nCn = 1 (n >= 1)
　nCr = 0 (r > n)
　nCr = n-1Cr + n-1Cr-1 (n > r > 0)
この式に従って再帰関数 unsigned int reccomb(int m, int n) を定義し，動作テストせよ．
ただし，関数 reccomb() には関数を呼び出した回数を数える機能を追加しておき，何回 reccomb() を呼び出したかも表示せよ．

なのですが、現在、下記の状況で行き詰まっています。
どのように再帰関数を使えばいいのか分からないのと、関数を呼び出した回数を数える方法が分かりません。

#include <stdio.h>

int count = 0;

int recfact(int n) {
	return (n <= 1 ? 1 : n * recfact(n - 1));
}

unsigned int reccomb(int m, int n) {
	count++;
	if (m >= 0 && n == 0) {
		return (1);
	}
	else if (m >= 1 && m == n) {
		return (1);
	}
	else if (m < n) {
		return (0);
	}
	else {
		
	}
}

int main(void) {
	int n, r;
	
	printf("n C r の n と r を入力せよ．\n");
	printf("n = "); scanf("%d", &n);
	printf("r = "); scanf("%d", &r);
	printf(" reccomb() の呼び出し回数：%d\n", count);
	printf(" n C r = %d\n", reccomb(n, r));
	return (0);
}

助言だけでもいいですので、よろしくお願いしますm(_ _)m

[組木紙織]

一言助言を
>printf(" reccomb() の呼び出し回数：%d\n", count);
>printf(" n C r = %d\n", reccomb(n, r));

この部分ですが、
一度もreccomb()を呼ばずにcountを使っているの分かりますか？
countはreccomb()を呼び出した後に使わないと、絶対に0になります。

[box]

> int recfact(int n) {
> 	return (n <= 1 ? 1 : n * recfact(n - 1));
> }

この関数は不要ですね。

> 	else {
> 		
> 	}

ここには、

> 　nCr = n-1Cr + n-1Cr-1 (n > r > 0)

この式の右辺をreturnするような文を書けばよいです。

[羽流布]

皆さん、助言ありがとうございますm(_ _)m
とりあえず、下記のような感じになったのですが、合っているのでしょうか？（特に呼び出し回数）

#include <stdio.h>

int count = 0;

unsigned int reccomb(int m, int n) {
	int comb = 0;
	
	if (m >= 0 && n == 0) {
		return (1);
	}
	else if (m >= 1 && m == n) {
		return (1);
	}
	else if (m < n) {
		return (0);
	}
	else {
		comb += reccomb(m - 1, n);
		++count;
		comb += reccomb(m - 1, n - 1);
		++count;
		return (comb);
	}
}

int main(void) {
	int n, r;
	
	printf("n C r の n と r を入力せよ．\n");
	printf("n = "); scanf("%d", &n);
	printf("r = "); scanf("%d", &r);
	printf(" n C r = %d\n", reccomb(n, r));
	printf(" reccomb() の呼び出し回数：%d\n", ++count);
	return (0);
}
/* 実行結果

n C r の n と r を入力せよ．
n = 32
r = 16
 n C r = 601080390
 reccomb() の呼び出し回数：1202160779

n C r の n と r を入力せよ．
n = 3
r = 2
 n C r = 3
 reccomb() の呼び出し回数：5

n C r の n と r を入力せよ．
n = 16
r = 12
 n C r = 1820
 reccomb() の呼び出し回数：3639

n C r の n と r を入力せよ．
n = 8
r = 4
 n C r = 70
 reccomb() の呼び出し回数：139

*/

[box]

> とりあえず、下記のような感じになったのですが、合っているのでしょうか？（特に呼び出し回数）

呼び出し回数は、reccomb()に入った直後に1回だけ加える方が、
多少なりともコード量が少なくてよいと思います。
今のままでも答えは正しいのですけれど。

また、組み合わせの数は、combという変数を使わなくても、式のとおりに

return reccomb(m-1, n) + reccomb(m-1, n-1);

と書く方がスッキリしているでしょう。

（追記）
実は、答えを早く求めるという観点からは、再帰呼び出しを使うと不利です。
最初の投稿で書かれていた階乗を計算する関数を使う方が、
計算時間の点では格段に有利です。

ところで、組み合わせの数と再帰呼び出し回数との間に
おもしろい関係があることにお気づきになりましたか？
時間があれば、なぜそういう関係があるのかについて
考えてみるのも一興でしょう。

[羽流布]

> box さん
確かにこのコードでは結果を表示するまでに結構かかりました。（特に数字が大きい場合）
先生も言ってましたが、まさかここまで長いとは思いませんでした。（私のパソコンのスペックが低いこともあるでしょうが）

コードは下記のようにスッキリさせました。

#include <stdio.h>

int count = 0;

unsigned int reccomb(int m, int n) {
	++count;
	if (m >= 0 && n == 0) {
		return (1);
	}
	else if (m >= 1 && m == n) {
		return (1);
	}
	else if (m < n) {
		return (0);
	}
	else {
		return (reccomb(m-1, n) + reccomb(m-1, n-1));
	}
}

int main(void) {
	int n, r;
	
	printf("n C r の n と r を入力せよ．\n");
	printf("n = "); scanf("%d", &n);
	printf("r = "); scanf("%d", &r);
	printf(" n C r = %d\n", reccomb(n, r));
	printf(" reccomb() の呼び出し回数：%d\n", count);
	return (0);
}

では、本当に助かりました（汗）

[組木紙織]

好みの問題になると思いますが、
次のように書いたらすっきりすると思います。

unsigned int reccomb(int m, int n) {
	++count;
	if (m >= 0 && n == 0) return (1);
	if (m >= 1 && m == n) return (1);
	if (m < n)            return (0);
	return (reccomb(m-1, n) + reccomb(m-1, n-1));
}

/*次はかなり細かい部分なので無視して下さってもかまいません。*/
引数は二項係数なので負になることは無いのでunsignedをつけたほうがいいのかな。
intだと負の値が入ったときを考える必要があるような気がします。
出題者側のミス、になるのかな。

戻り値にはunsignedがついているので少しきになりました。