12/17 : 再帰

階乗を計算するプログラムは次のように書ける.

def factorial(N) {
    F = 1;
    for ( I = 1; I <= N; I++ )
        F *= I;
    return F;
}

ここで, $n! = n\cdot (n-1)!$ だから次のようにも書ける.

def rfactorial(N) {
    if ( N == 1 )
        return 1;
    else
        return N*rfactorial(N-1);
}

あるいは, 短いプログラムが好きなら

def rfactorial(N) { return N==1 ? 1 : N*rfactorial(N-1); }

という書き方もできる. このように, 関数の実行中に自分自身を 呼び出すことを再帰 (recursion) という.

• 再帰の利点

  プログラムが書きやすい場合がある. (パラメタの数が少ない場合 に帰着できる場合など.)

  問題の構造上, 再帰で書かざるを得ない場合もある.

• 再帰の欠点

  通常のループで書けるプログラムを再帰で書くと一般に効率は落ちるが, これは実行機構による.

  それ以上に大変なことになる場合もある.

例 16.1   隣接 3 項間の漸化式

$$a_n = Aa_{n-1}+Ba_{n-2} \quad a_1 = 1, a_2 = 1$$

を

def a(N) {
    if ( N == 1 || N == 2 )
        return 1;
    else
        return A*a(N-1)+B*a(N-2);
}

と書いたとする. このとき, 例えば $a(5)$ の計算を考えると $a(4)$, $a(3)$ が独立に計算されるが, $a(4)$ の計算でも $a(3)$ の計算が必要になるので, 結局 $a(3)$ は二回計算されてしまう. 計算量 $T(n)$ を大雑把に見積もると

$$T(N) = T(N-1)+T(N-2)+3$$

(3 はかけ算 2 回, 足し算 1 回のつもり) より, フィボナッチ数列 の第 $N$ 項を $f_N$ とすれば $T(N) \ge f_N$ より $T(N)$ は 指数的になってしまう. 非再帰なら $O(N)$ なのでこれはあまりに ひどい.

こういうことに注意して使うこと.

例 16.2   リストの結合 (要素の順序は変えない).

$$[1,2,3]+ [4,5,6] \rightarrow [1,2,3,4,5,6]$$

def list_append(A,B) {
    if ( A == [] )
        return B;
    else {
        L1 = list_append(cdr(A),B);
        return cons(car(A),L1);
    }
}

これは,

$$[a_1,a_2,...,a_n]+ [b_1,b_2,...] = [a_1] + [a_2,...,a_n,b_1,b_2,...]$$

ということである.

演習 16.1   リストの結合を, 再帰およびリスト $L$ の $K$ 番目の要素取り出し $L[K]$ を使わずに書け. (ヒント : リストの反転が使える.)

例 16.3   ある順序で整列したリストに要素を追加し, 結果がまた整列している ようにする関数. 例えば, 大きい順に並んでいるリスト List に要素 A を追加する関数は次のように書けばよい.

def list_insert(A,List) {
    if ( List == [] )
        return [A];
    else if ( A >= car(List) )
        return cons(A,List);
    else {
        /* 先頭は car(List); A は cdr(List) に insert すればよい */
        L1 = list_insert(A,cdr(List);
        return cons(car(List),L1);
    }
}

演習 16.2   list_insert を使って, リストを大きい順に整列するプログラム を書け.

再帰が本質的に必要な場合もある.

例えば, リストの各要素は実はなんでもよい. 特にまたリストで あってもよい.

例 16.4   リストに現れる全ての数字の和を求める関数.

def add_all(Obj) {
    if ( type(Obj) <= 1 ) /* Obj is a number */
        return Obj;
    else if ( type(Obj) == 4 ) {
        /* Obj is a list */
        if ( Obj == [] )
            return 0;
        else {
            A = add_all(car(Obj));
            B = add_all(cdr(Obj));
        return A+B;
        }
    } else
        error("add_all : invalid argument");
}

[1] add_all([1,[2,[3,4],5],[6,7,8],9,[[],11,[12]]]);
68

ここで, type(Obj) は Obj の型を調べる関数で

Obj	0	0 でない数	多項式	有理式	リスト	配列
type(Obj)	0	1	2	3	4	5

演習 16.3   リストの要素を一列に並べる関数を書け.

$$[1,2,[3,[4,5]],6,[7,8]] \rightarrow [1,2,3,4,5,6,7,8]$$

という操作を行うという意味である. (list_append を使ってよい.)

演習 16.4   与えられたリストの要素を並べ変えて得られる全てのリストから なるリストを返す関数を書け.

演習 16.5   与えられたリストの要素から K 個を選ぶ全ての組合せのリスト からなるリストを返す関数を書け.

注意 16.1   再帰は局所変数により実現されていることに注意する.