再帰基礎の演習
再帰は、関数が自分自身を呼び出すことで、データの構造に合わせた「繰り返し」処理を行うことができる
例1 1から100までの総和を計算する
総和は、1 + 2 + .... + 100 のように足し算を繰り返すことで計算できる
再帰ではすこし考え方を変更して
総和は 1 + 「2から100までの総和」 で計算できる。
というように、先に a から b までの総和ができるものとして、その結果を使う
プログラム風に書けば sum(1, 100) は 1 + sum(2, 100) ということで、 sum(a, b) は a + sum(a+1, b) となる
結果として再帰も繰り返しをしていることと等しい。
code: recursivesum.c
int sum(int a, int b){
if(a >= b){
return a;
}
return( a + sum(a+1, b));
}
int main(void){
printf("%d\n", sum(1, 100));
}
例2 再帰的な問題を再帰で扱う
倉庫から荷物を運ぶ方法を考える。一個取り出す機械 A と、二個取り出す機械 B がある。
倉庫の荷物が 1 なら、Aを使い一回取り出して終わり
倉庫の荷物が 2つなら、AA として取り出すか B と取り出すか２通りの方法がある
倉庫の荷物が 3つなら、AAA、AB、BA の３通りの方法がある
倉庫の荷物が 10個のとき、取り出す方法は何とおりあるか
まず、A で取り出すか B で取り出すかの２通りに分かれ、それぞれ残りの回数は再帰で求められる
Aで取り出すと残りは n-1 個、Bで取り出すと残りは n-2個なので
renimotsu( n) は、renimotsu(n-1) + renimotsu(n-2) となる
code: recursivnimotsu.c
int renimotsu(int n){
if(n == 1) return 1;
if(n == 2) return 2;
return renimotsu(n-1) + renimotsu(n-2); //Aでとりだしたあとの方法 + Bでとりだしたあとの方法
}
int main(void){
int n;
for(n=1; n<10; n++){
printf("%d %d\n", n, renimotsu(n) );
}
}
（この数値の並びはフィボナッチ数列になっている）
クイズ
演習問題
1) aからbまでの積を計算するプログラムを書こう
code: mul.c
int remul(int a, int b){
...
}
int main(void){
printf("%d\n", remul(1, 10));
}
2) nが素数かどうか判断する関数を再帰で書いてみた。実行してみよう。
code: ressosu.c
/* n が i 以上 n 未満の素数を素因数に持たないか判断する関数 */
int is_sosu_greaterthani(int n, int i){
if(i<=1) { printf("error\n"); exit(1);} // i が範囲外
if(n<=i) return 1; //i以上n未満の数がない（ので持たない）
if(n%i == 0 ) return 0; // 素因数を持ってた
return is_sosu_greaterthani(n, i+1); // その他のi以上のチェックは再帰にまかせる
}
int main(void){
int n;
for(n=2; n<100; n++){
if(is_sosu_greaterthani(n, 2) ){
printf("sosu %d\n", n);
}
}
}
3) n番めのフィボナッチ数 fib(n) を求めるプログラムを書こう
fib(0)=0, fig(1)=1 とする
4) 配列 a 内の最小値を求めるプログラムを main() 関数を補って実行しよう
例えば128個のデータが a[0] ... a[127] に入っているとき
全体の最小値は、配列の前半 a[0] ... a[63] の最小値と、配列の後半a[64] ... a[127] の最小値の小さい方。 前半、後半、それぞれ半分の最小値は再帰で求める。
半分の境目 63と64 は 平均値から求めることができる。整数は切り捨てになることを利用する。
code: saisyo.c
int saisyou(int a[], int left, int right){
int ls, rs;
// 半分にできないときは終わり。その値そのものが最小値。
if(left >= right) return aleft; ls = saisyou(a, left, (left+right)/2 );
rs = saisyou(a, (left+right)/2 + 1, right );
return (ls < rs) ? ls : rs ; //三項演算子
}
三項演算子 「 ? と : 」は (条件) が正しければ (条件) ? A : B のときの A を値とし、条件が偽なら B を値にする。