nCrを求める関数

[yuu]

再帰関数を学んでるのですがこの処理の意味がまったくわかりません
nCrを求めるプログラムの関数なんですけど
なぜこの関数で求められるのでしょうか？

コード:

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

[box]

なぜこの関数で求められるのでしょうか？

パスカルの三角形について調べてみると、幸せになれるかもしれません。
ところで、もう少しまともなインデントはできないものでしょうか。
例えば下のように。

コード:

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

[beatle]

数学における「組み合わせ」の知識があるかないかですね。
n個のうちr個取る組み合わせの数は、以下の2通りの場合の数を足せば求まります。

• n-1個のうちr個取って、残り1個は取らない
• n-1個のうちr-1個取って、残り1個を取る

この2つの場合は排反ですから、2つの場合の数を足していいのです。