(44.1) ある関数の中でその関数自身を呼び出すことを「再帰」という。 ある程度のプログラミング体験を積んで 「ここは再帰を用いてもよい」 「用いるべきだ」 という判断ができるまでは、自分の判断で再帰を使うことは避けたほうがよい。 クイックソートでは再帰を用いる。 きょうはその練習である。
(44.2) 最大公約数を返す関数を再帰を用いて書いてみたもの。
#include <stdio.h>
#include <stdlib.h> /* srand() */
#include <time.h> /* time() */
int gcd(int x, int y);
int gcd0(int x, int y);
main() {
int i, x, y;
srand((unsigned)time(NULL)); /* 現在時刻で乱数の種を初期化 */
for (i = 0; i < 30; i++) { /* 乱数を引数にして gcd(), gcd0() を試す */
x = rand() % 100; y = rand() % 100;
printf("gcd(%d, %d) = %d, ", x, y, gcd(x,y));
printf("gcd(%d, %d) = %d\n", x, y, gcd0(x,y));
}
}
/* 非負整数 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;
for ( ; y != 0; ) {
r = x % y;
x = y;
y = r;
}
return x;
}
(44.3) どちらの関数も、エウクレイデース（ユークリッド）の互除法を使っている。 再帰を使わないバージョンについては、各自でこれでよいことを確かめられたい。 再帰バージョンを、gcd(60, 24) として呼び出したとする。 するとこの関数が gcd(24, 12) を呼び出し、 それがさらに gcd(12, 0) を呼び出し、これは 12 を返す。 するとそれが順に返されて、全体として 12 が返ることになる。
(44.4) その場合、gcd(60, 24) の実行が終わる前に gcd(24, 12) が呼び出される。 その実行が終わる前に gcd(12, 0) が呼び出される。 つまり、ある時点では三つの gcd() が同時に動いている。 これがあまりに多すぎると、メモリを使い果たしてしまい、プログラムは正しく動かない。
(44.5) プログラムの動きを頭の中で考える際、 再帰呼び出しのところでその関数の冒頭に戻ると考えると混乱することが多い。 考えないか、考えるなら、その関数の“コピー”の冒頭に移ると考えよ。 （実際には、 関数 gcd() はプログラムの中に一つだけ書く。そうでないとエラーになる。）
main() {
...
+-> g = gcd(60, 24);
| ...
+----------------+
|
} |
|
: | |
60 : 24 | 24 12 | 12 0
int gcd(int x, int y) { | +-> int gcd(int x, int y) { | +-> int gcd(int x, int y) {
: | | ... | | ...
+-> r = gcd(x, x % y); --|-+ +-> r = gcd(y, x % y); --|-+ return x;
| 24 12 | | 12 0 | 12
| : | | | |
| : | +------------------------|----------------+
| return r; | | return r; |
| 12 ---+ | 12 |
| | | |
+------------------------|----------------+ |
| |
関数 gcd() 関数 gcd() のコピー 関数 gcd() のコピーその２
(44.6) 次は、配列の中から最大のものの添え字を見つける関数を、 クイックソートの練習のため、わざと再帰を使って書いたものである。 再帰の「深さ」とは、その関数が何重に呼び出されているか、である。 ここでは、最初に呼び出されたときは深さ 0 であり、 深さ i で呼び出された関数から呼び出されたときは深さ i+1 である、と定義する。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 20
int a[N+1];
int mymax(int d, int from, int to);
main() {
int i;
srand((unsigned)time(NULL));
for (i = 1; i <= N; i++) { /* 添え字の印字 */
printf("%2d ", i);
}
printf("\n");
for (i = 1; i <= N; i++) {
a[i] = rand() % 100; /* 初期化 */
printf("%2d ", a[i]); /* 配列の値の印字 */
}
printf("\n");
printf("a[%d] が最大（のものの一つ）です.\n", mymax(0, 1, N));
}
/* a[from] から a[to] までの中から最大のものの添字を返す。*/
/* わざと再帰を使ってある。d は再帰の深さ。 */
int mymax(int d, int from, int to) {
int i, j, k, n;
for (n = 0; n < d; n++) { /* d の値の二倍だけスペースを */
printf(" "); /* 印字することで深さを示す */
}
printf("mymax(%d, %d) として呼び出されました.\n", from, to);
if (from == to) {
return from;
} else {
k = rand() % (to - from) + from; /* 切れ目 k を乱数で決める */
/* (from 以上 to 未満の範囲で) */
i = mymax(d + 1, from, k); /* 再帰呼び出し */
j = mymax(d + 1, k + 1, to); /* 同 */
if (a[i] >= a[j]) { /* 大きいほうの添字を返す */
return i;
} else {
return j;
}
}
}
(44.7) 初めは main() から mymax(0, 1, 20) として呼び出される。 この関数は a[from] から a[to] までのうちで最大のもの（の一つ）の添え字を返すのだが、 乱数で切れ目 k の値を決め、もしもそれが 6 だったとすると mymax(1, 1, 6) として自分自身を呼び出し、 次に mymax(1, 7, 20) として自分自身を呼び出し、 それらが返した添え字のうちで値が大きいほうの添え字を返す。 呼び出された mymax(1, 1, 6) と mymax(1, 7, 20) はまた自分自身を呼び出す。 同時に呼び出されている関数の数は、配列がうまく半分ずつに分かれてゆけば log2(N) 程度だが、 運が悪いと N に近くなる。
(44.8) 上のプログラムで、a[i] = rand() % 100; を a[i] = i; に変え、 関数 mymax() の中の k = rand() % (to - from) + from; を k = from; または k = to - 1; で置き換えると、 最も“運の悪い”場合になる。試してみよ。
(44.9) また、上の二つの例から、 「再帰を用いた関数は中で場合分けを行ない、 自明な場合にはすみやかに return し、 非自明な場合には“より自明に近い”引数で自分自身を呼び出す」という形になることがわかるであろう。 数学的帰納法による証明と似ている面がある。
(44.10) 次は積を返す関数だが、再帰が深くなりすぎるのでよくない。 （そもそも、x*y でよい。）
int mul(int x, int y) {
if (y == 0) {
return 0;
} else {
return mul(x, y-1) + x;
}
}
(44.11) 次はまちがったプログラムである。 次々と自分自身を呼び出し、メモリを使い果たす。
int mul(int x, int y) {
return mul(x, y);
}
(45.1) 階乗を求める関数 int factorial(int n) を再帰を用いて書け。
(45.2) n が偶数 2k のとき xn = (xk)2, n が奇数 2k+1 のとき xn = x(xk)2 を利用して x の n 乗を求める関数 int power(int x, int n) を書け。 （0 の 0 乗になる場合のことは考えなくてよい。）
(45.3) nCr = n-1Cr + n-1Cr-1 を利用して nCr を求める関数 int comb(int n, int r) を書け。
(45.4) 自然数 n を素因数分解するには、 2, 3, 4, ... で順に割ってみることで一番小さな素因数 p を見つけ、 あとは n/p を素因数分解すればよい。 このアイディアに沿って、 再帰を用いて自然数を素因数分解するプログラムを書け。 （再帰を用いなくても書ける。）
(45.5) 「ハノイの塔」とは、次のようなゲームである。
| | |
1|1 | |
22|22 | |
333|333 | |
4444|4444 | |
55555|55555 | |
666666|666666 | |
7777777|7777777 | |
88888888|88888888 | |
=====================================================================
この規則のもとで、 n 枚の円盤を、棒 1 に移動せよ。---
解法があることは、n に関する数学的帰納法で示せる。 n が 1 のときは円盤が一枚だけだから、単に移動すればよい。 n-1 のときの解法がわかっていれば、 まずは小さいほうから n-1 枚の円盤を、 規則に従って棒 2 に移すことができる。 次に、一番大きな円盤を空いている棒 1 に移す。 それから、n-1 枚の円盤をその上に移せばよい。 これが最少手数で移動を行なう方法なので、 n 枚の場合の手数は 2n-1 である。 オリジナルの問題は n が 64 なので、 264-1 = 18446744073709551615 手かかる。 一秒につき一手で動かしても、5845 億年以上かかることになる。
小さいほうから数えて i 枚の円盤を棒 from から棒 to へ移動する方法を
円盤 1 を棒 0 から棒 1 へ移動します. 円盤 2 を棒 0 から棒 2 へ移動します. 円盤 1 を棒 1 から棒 2 へ移動します. 円盤 3 を棒 0 から棒 1 へ移動します. 円盤 1 を棒 2 から棒 0 へ移動します. 円盤 2 を棒 2 から棒 1 へ移動します. 円盤 1 を棒 0 から棒 1 へ移動します.のように表示する関数 void hanoi(int i, int from, int to) を書け。 （この例では i は 3 である。）