(7.1.1) 「計算数学ｂ」で取り組むクイックソートで用いる手法，「再帰」の練習である。
(7.1.2) 例・練習問題には， 再帰を用いることが適切でないものも含まれている。 つまり，無理をして，あるいは無駄に，再帰を使っているものがある。 どれがそれにあたるかを考え， 再帰を使わずに書いてみるのはよい練習になるだろう。 （ただし，再帰を用いることが適切かどうかは， コンピュータの速度などに依存するので， 必ずしも，一意に決めることはできないと思う。）
(7.2.1) ある関数の中でその関数自身を呼び出すことを「再帰」呼び出しという。 ある程度のプログラミング体験を積んで 「ここは再帰を用いてもよい」 「用いるべきだ」 という判断ができるまでは，自分の判断で再帰を使うことは避けたほうがよい。
(7.2.2) 最大公約数を返す関数を再帰を用いて書いてみたもの。
#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++) { /* 乱数を引数にして 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;
}
(7.2.3) どちらの関数も，エウクレイデース（ユークリッド）の互除法を使っている。 再帰を使わないバージョンについては，各自でこれでよいことを確かめられたい。 再帰バージョンを，gcd(60, 24) として呼び出したとする。 するとこの関数が gcd(24, 12) を呼び出し， それがさらに gcd(12, 0) を呼び出し，これは 12 を返す。 するとそれが順に返されて，全体として 12 が返ることになる。 （関数 gcd() の中の printf() 文がコメントになっているが， この文を実行させると，過程がわかりやすいかもしれない。）
(7.2.4) その場合，gcd(60, 24) の実行が終わる前に gcd(24, 12) が呼び出される。 その実行が終わる前に gcd(12, 0) が呼び出される。 つまり，ある時点では三つの gcd() が同時に動いている。 これがあまりに多すぎると，メモリを使い果たしてしまい，プログラムは正しく動かない。
(7.2.5) プログラムの動きを頭の中で考える際， 再帰呼び出しのところでその関数の冒頭に戻ると考えると混乱することが多い。 考えないか，考えるなら，その関数の“コピー”の冒頭に移ると考えよ。
int 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(y, x % y); --|-+ +-> r = gcd(y, x % y); --|-+ return x;
| 24 12 | | 12 0 | 12
| : | | | |
| : | +------------------------|----------------+
| return r; | | return r; |
| 12 ---+ | 12 |
| | | |
+------------------------|----------------+ |
| |
関数 gcd() 関数 gcd() のコピー 関数 gcd() のコピーその２
実際には， 関数 gcd() はプログラムの中に一つだけ書く。そうでないとエラーになる。
(7.2.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);
int 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;
}
}
}
(7.2.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 に近くなる。
(7.2.8) 上のプログラムで， 関数 mymax() の中の k = rand() % (to - from) + from; を k = from; または k = to - 1; で置き換えると， 最も“運の悪い”場合になる。試してみよ。
(7.2.9) また，上の二つの例から， 「再帰を用いた関数は中で場合分けをおこない， 自明な場合にはすみやかに return し， 非自明な場合には“より自明に近い”引数で自分自身を呼び出す」という形になることがわかるであろう。 数学的帰納法による証明と似ている面がある。
(7.2.10) 次は積を返す関数だが，再帰が深くなりすぎるのでよくない。 （そもそも，x*y でよい。）
int mul(int x, int y) {
if (y == 0) {
return 0;
} else {
return mul(x, y-1) + x;
}
}
(7.2.11) 次はまちがったプログラムである。 次々と自分自身を呼び出し，メモリを使い果たす。
int mul(int x, int y) {
return mul(x, y);
}
(7.3.1) 階乗を求める関数 int factorial(int n) を再帰を用いて書け。
(7.3.2) n が偶数 2k のとき xn = (xk)2, n が奇数 2k+1 のとき xn = x(xk)2 を利用して x の n 乗を求める関数 int power(int x, int n) を書け。 （0 の 0 乗になる場合のことは考えなくてよい。）
(7.3.3) nCr = n-1Cr + n-1Cr-1 を利用して nCr を求める関数 int comb(int n, int r) を書け。
付）再帰を使わないで書く際に使う（かもしれない），二重配列について説明する。
int a[3][4];
と宣言すると，0 ≦ i ＜ 3, 0 ≦ j ＜ 4 なる整数 i, j に対し int 型変数 a[i][j] が使える。
(7.3.4) 自然数 n を素因数分解するには， 2, 3, 4, ... で順に割ってみることで一番小さな素因数 p を見つけ， あとは n/p を素因数分解すればよい。 このアイディアに沿って， 再帰を用いて自然数を素因数分解するプログラムを書け。 （再帰を用いなくても書ける。）
(7.3.5) 「ハノイの塔」とは，次のようなゲームである。
| | |
1|1 | |
22|22 | |
333|333 | |
4444|4444 | |
55555|55555 | |
666666|666666 | |
7777777|7777777 | |
88888888|88888888 | |
=====================================================================
この規則のもとで， n 枚の円盤を，棒 1 に移動せよ。---
解があることは，n に関する数学的帰納法で示せる。 n が 0 のときは何もしなくてよい。 n-1 のときの解がわかっていれば， まずは小さいほうから n-1 枚の円盤をその場合の解に従って棒 2 に移すことができる。 次に，一番大きな円盤を空いている棒 1 に移す。 それから，n-1 枚の円盤をその上に移せばよい。 これが最少手数で移動をおこなう方法なので， n 枚の場合の手数は 2n-1 である。 オリジナルの問題は n が 64 なので， 264-1 = 18446744073709551615 手かかる。 一秒につき一手で動かしても，5845 億年以上かかることになる。
小さいほうから数えて i 枚の円盤を棒 from から棒 to へ移動する方法を， 次のように表示する関数 void hanoi(int i, int from, int to) を書け。 （この例では i は 3 である。）
円盤 1 を棒 0 から棒 1 へ移動します. 円盤 2 を棒 0 から棒 2 へ移動します. 円盤 1 を棒 1 から棒 2 へ移動します. 円盤 3 を棒 0 から棒 1 へ移動します. 円盤 1 を棒 2 から棒 0 へ移動します. 円盤 2 を棒 2 から棒 1 へ移動します. 円盤 1 を棒 0 から棒 1 へ移動します.
(7.3.6) Fibonacci 数列の第 n 項を返す関数を，再帰を用いて書け。 また，再帰を用いないで書け。 （再帰を用いないプログラムには，配列を使うものと使わないものとがある。）
(7.3.7) Zermelo-Fraenkel の公理系では，0 は空集合のことと定義し， n は集合 {0, 1, 2, ..., n-1} のことと定義する。 つまり， 1 は {0}, 2 は {0,{0}}, 3 は {0,{0},{0,{0}}} となる。 このスタイルで自然数を出力する関数を書け。
余談：このスタイルで n を表すには何文字が必要か？