再帰とは、ある関数の中でその関数自身を呼び出すことである。
最大公約数を返す関数を再帰を用いて書いてみたもの。
#include <stdio.h>
#include <stdlib.h> /* srand() */
#include <time.h> /* time() */
int gcd(int x, int y);
int gcd0(int x, int y);
int main() {
int i, x, y;
srand((unsigned)time(NULL)); /* 現在時刻で乱数の種を初期化 */
for (i = 0; i < 30; i++) {
x = rand() % 1000; y = rand() % 1000;
printf("gcd(%d, %d) = %d, ", x, y, gcd(x,y));
printf("gcd(%d, %d) = %d\n", x, y, gcd0(x,y));
}
return;
}
/* 非負整数 x, y の最大公約数を返す。再帰バージョン。どちらが大きくてもよい */
int gcd(int x, int y) {
/* printf("%d と %d の最大公約数を求めます.\n", x, y); */
if (y == 0) {
return x;
} else {
return gcd(y, x % y);
}
}
/* 同上。再帰を使わないバージョン */
int gcd0(int x, int y) {
int r;
while ((r = x % y) != 0) {
x = y; y = r;
}
return y;
}
配列の中から最大のものを見つける関数を、 わざと再帰を使って書いたもの。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 16
int a[N];
int mymax(int d, int from, int to);
main() {
int i;
srand((unsigned)time(NULL));
for (i = 0; i < N; i++) { /* 初期化 */
a[i] = rand() % 100;
}
for (i = 0; i < N; i++) { /* 印字 */
printf("%2d ", a[i]);
}
printf("\n");
printf("a[%d] が最大（のものの一つ）です.\n", mymax(0, 0, N-1));
return 0;
}
/* a[from] から a[to] までの中から最大のものの添字を返す。*/
/* わざと再帰を使ってある。d は再帰の深さ。 */
int mymax(int d, int from, int to) {
int i, j, n;
for (n = 0; n < d; n++) { /* d の値の二倍だけ */
printf(" "); /* スペースを印字 */
}
printf("mymax(%d, %d) として呼び出されました.\n", from, to);
if (from == to) {
return from;
} else {
i = mymax(d + 1, from, (from + to) / 2);
j = mymax(d + 1, (from + to) / 2 + 1, to);
if (a[i] >= a[j]) {
return i;
} else {
return j;
}
}
}
ハノイの塔。
#include <stdio.h>
#define N 6 /* 円盤の枚数 */
void hanoi(int i, int from, int to);
main() {
hanoi(N, 0, 1);
}
/* 円盤 1 から i までを棒 from から棒 to へ移す */
void hanoi(int i, int from, int to) {
if (i == 1) {
printf("円盤 1 を棒 %d から棒 %d へ.\n", from, to);
} else {
hanoi(i - 1, from, 3 - from - to);
printf("円盤 %d を棒 %d から棒 %d へ.\n", i, from, to);
hanoi(i - 1, 3 - from - to, to);
}
}
次は積を返す関数だが、再帰が深くなりすぎるのでよくない。
int mul(int x, int y) {
if (y == 0) {
return 0;
} else {
return mul(x, y-1) + x;
}
}
次はまちがったプログラムである。 永遠に終了しない。
int mul(int x, int y) {
return mul(x, y);
}
a[0] ... a[N-1] から一つの元を選び、その値を pivot とする。 このとき、N に比例する計算量でこれらを並びかえて、
pivot の値がうまく選ばれれば、上組と下組はほぼ同数の元からなる。 次のステップで上組と下組をそれぞれ二つに分ける計算量はそれぞれ N/2 である。 さらに次のステップでは N/4 が四回。 よって、この場合、 全体の計算量は N にくり返しの回数をかけたものになる。 くり返しの回数はほぼ log(N) だから、 全体の計算量は Ο(N log(N)) である。 ヒープソートも Ο(N log(N)) だったが、 クイックソートのほうが平均すると速いそうである。
しかし、 毎回上組または下組が空になれば、くり返しの回数はほぼ N になり、 全体の計算量は Ο(N2) となる。 また、この場合、 N の値が大きいと stack overflow という現象を起こし、 プログラムの実行が途中で終わってしまうこともある。 （しかし、この現象の避けかたまではこの授業では考えないことにする。 配列を乱数で初期化する限り、このようなことは滅多に起こらない。）
関数 void quicksort(int left, int right) の準備版を書け。 この関数は、
printf("pivot は a[%d] = %d です.\n", left, a[left]);
と書いておくとわかりやすい。
最後には
printf("次は a[%d] から a[%d] までと ", left, i-1);
printf("a[%d] から a[%d] まで\n", i+1, right);
と書いておくと、
i が正しくセットされたかどうかがわかりやすいだろう。
main() では quicksort(0, N-1); としてこの関数を呼び出す。 init(), print(), swap() は前と同じ。 N は 10 ぐらいで十分である。
注１） pivot がその範囲の最小値の場合は 「a[0] から a[-1] まで」のように出力されるかもしれないが、 それで構わない。 最大値の場合も同様。
課題 7-1) クイックソートのプログラムを書き、課題 4-1 と同じようなことを調べよ。
（上の演習問題が済んでいれば、 関数 void quicksort(int left, int right) の最後に
quicksort(left, i-1);
quicksort(i+1, right);
と書き加えるだけである。）
課題 7-2) 課題 4-2 と同様のことを、クイックソートについて調べよ。
課題 7-3) 比較の回数も数えてみよ。
以上から適当に選んで、メールでレポートしてください。
プログラムも送ってください。 その際、Active!Mail のメール作成画面の「添付ファイル」 *ではなく* 本文の中にソースファイルを貼りつけること。
所要時間を計るにせよ回数を数えるにせよ、 数回くり返して測定し、それらのデータそのものおよび平均値をレポートに書くこと。 それから、理論上の値などと比較すること。 感想は書かなくてもよい。
宛て先は私（岩瀬）の実習用アカウント cf5326@mailedu1.ipc.kanazawa-u.ac.jp です。 件名は「kadai7」（←全て半角文字、アルファベットは小文字、 途中にスペースをいれない）としてください。 自分の学籍番号、氏名（として大学に届けてあるもの） をメールの *本文内にも* 書くのを忘れずに。
その１． 関数 void init(void) の中の a[i] = rand(); を a[i] = i + rand() % 5; と変えれば、 ほぼ昇順にソートされたデータで初期化することになる。 a[i] = N - i + rand() % 5; とすればほぼ降順。 これらの場合の交換回数・比較回数を調べよ。 いままでに書いたほかのソートではどうなるか？ （5 は適当に選んだ定数であって意味はないので、変えてもよい。）
その２． 再帰の例としてあげた関数 int mymax() を参考にして、 クイックソートの再帰の最大の深さを調べよ。 ただし、引数の d とは別に、 変数 count などと同じく、 main() の外で int depth = 0; として大域変数を宣言する。 それと d とをどう結びつけるかは各自で考えること。