2007 年度「計算数学１」 2007-07-05

§56 再帰

(56.1) ある関数の中でその関数自身を呼び出すことを「再帰」という。 ある程度のプログラミング体験を積んで 「ここは再帰を用いてもよい」 「用いるべきだ」 という判断ができるまでは、自分の判断で再帰を使うことは避けたほうがよい。 クイックソートでは再帰を用いる。 きょうはその練習である。

(56.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() % 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));
    }
}


/* 非負整数 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;
}

(56.3) どちらの関数も、エウクレイデス（ユークリッド）の互除法を使っている。 再帰を使わないバージョンの説明は省略しよう。 再帰バージョンを、gcd(60, 24) として呼び出したとする。 するとこの関数が gcd(24, 12) を呼び出し、 それがさらに gcd(12, 0) を呼び出し、これは 12 を返す。 するとそれが順に返されて、全体として 12 が返ることになる。

(56.4) その場合、gcd(60, 24) の実行が終わる前に gcd(24, 12) が呼び出される。 その実行が終わる前に gcd(12, 0) が呼び出される。 つまり、ある時点では三つの gcd() が同時に動いている。 これがあまりに多すぎると、メモリを使い果たしてしまい、プログラムは正しく動かない。

(56.5) 次は、配列の中から最大のものの添え字を見つける関数を、 クイックソートの練習のため、わざと再帰を使って書いたものである。 再帰の「深さ」とは、その関数が何重に呼び出されているか、である。 すなわち、最初に呼び出されたときは深さ 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++) {          /* 初期化 */
        a[i] = rand() % 100;
    }
    for (i = 1; i <= N; i++) {          /* 印字 */
        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 を決める (from 以上 to - 1 以下の範囲に) */
        k = rand() % (to - from) + from;

        i = mymax(d + 1, from, k);      /* 再帰呼び出し */
        j = mymax(d + 1, k + 1, to);    /*      同      */

        if (a[i] >= a[j]) {     /* 大きいほうの添字を返す */
            return i;
        } else {
            return j;
        }
    }
}

(56.6) 初めは 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) はまた自分自身を呼び出す。 同時に呼び出されている数は、配列がうまく半分ずつに分かれてゆけば log₂(N) 程度だが、 運が悪いと N に近くなる。 （再帰の深さが 1 だけ増すごとに呼び出される関数の数は二倍に増えるが、 同時に呼び出されている関数の数は指数関数的には増えない。）

(56.7) また、上の二つの例から、 「再帰を用いた関数は中で場合分けを行ない、 自明な場合にはすみやかに return し、 非自明な場合には“より自明に近い”引数で自分自身を呼び出す」という形になることがわかるであろう。

(56.8) 次は積を返す関数だが、再帰が深くなりすぎるのでよくない。 （そもそも x*y と書けばよいだけのこと。）

int mul(int x, int y) {
    if (y == 0) {
        return 0;
    } else {
        return mul(x, y-1) + x;
    }
}

(56.9) 次はまちがったプログラムである。 次々と自分自身を呼び出し、メモリを使い果たしてしまう。

int mul(int x, int y) {
    return mul(x, y);
}

§57 練習問題

(57.1) 階乗を求める関数 int factorial(int n) を再帰を用いて書け。 返り値の型は double 型にしてもよい。

(57.2) x の n 乗を、

• n が偶数 2k のとき xⁿ = (x^k)²,
• n が奇数 2k+1 のとき xⁿ = x(x^k)²

(57.3) _nC_r = _n-1C_r + _n-1C_r-1 を利用して _nC_r を求める関数 int comb(int n, int r) を書け。

(57.4) 「ハノイの塔」で、棒の番号を 0, 1, 2 とする。 i 枚の円盤を棒 from から棒 to へ移動する方法を

0 から 1 へ移動します. 0 から 2 へ移動します. 1 から 2 へ移動します. 0 から 1 へ移動します.
2 から 0 へ移動します. 2 から 1 へ移動します. 0 から 1 へ移動します.