Ｃアルゴリズム 組み合わせ(再帰)

数学的な説明はしませんが組み合わせは漸近式で求めることができます漸近式は単純な計算を繰り返すため再帰を作る問題でよく使われます。

#include＜stdio.h＞

main(){
　　　　long combi(int ,int);
　　　　int n,r;

　　　　printf("Input nCr n,r : ");
　　　　scanf("%d %d",&n,&r);
　　　　printf("%dC%d = %d",n,r,combi(n,r));
}

long combi(int n, int r){
　　　　if(r == 0 || r == n) return 1;
　　　　else return (n - r + 1) / r * combi(n,r-1);
}

Ｃアルゴリズム ユークリッドの互除法(再帰)

再帰プログラムの中では総和(Sum),階乗,ハノイの塔に続く最初に覚えるアルゴリズムのひとつです。再帰プログラムは繰り返し、条件分岐の次に覚えるプログラムで主に単純作業の繰り返しに利用されます。頭の中では理解しづらいので実際にトレースし紙に書き起こすなどしてプログラムの動きを理解していくとよいでしょう。

#include＜stdio.h＞

main(){
　　　　int x,y;
　　　　int gcd(int, int);　　/*ユークリッドの互除法の計算*/

　　　　printf("input x y : ");
　　　　scanf("%d %d", &x, &y);
　　　　printf("%d",gcd(x,y));
}

int gcd(int x, int y){
　　　　if(y == 0) return x;　　　/*終了条件*/
　　　　else　　 return gcd(y, x % y);　/*ユークリッドの互除法*/
}