人気ブログランキング | 話題のタグを見る

再帰のちから

整数 n の階乗の定義を整数を降順に整列すると次のようになる。

n! = n * (n-1) * ... * 2 * 1

これは、明示的に n から順番に 1 まで整数の掛け算を行うことを示している。しかし、この式は次のように変形できる。

n! = n * (n-1)!

この定義ではまだ分かっていない n-1 の階乗を分かっているものとしてそれに n を掛けている。こんないい加減な定義でも次のように展開していくと、ちゃんと上のような計算になる。

n!
= n * (n-1)!
= n * (n-1 * (n-2)!)
= n * (n-1 * ( (n-2) * ( .... * (3 * (2 * 1))))...)

ただし、1! = 1 であることを断っておかないと上の展開は永遠に続いて終わらなくなってしまう。無限の再帰的展開を終わらせる 1! = 1 のようなものを終了条件という。再帰的定義にはこのように再帰的定義の式(漸化式)と終了条件が必要だ。

上のような再帰的定義は Scheme ではそのままプログラムすることができる。

(define (fact n)
  (if (= n 1)
      1
      (* n (fact (- n 1)))))

(fact 5) => 120

これくらいの再帰関数なら他の言語でも簡単に記述できる。だが、Scheme は, 次のような木構造のデータも再帰で簡単に処理することができる。


^
1 ^
2 ^
^ 5
3 4


次の関数は、上の木構造の葉の数をすべて数えるプログラムだ。

(define (count-leaf tree)
  (cond ((null? tree) 0)
        ((not (pair? tree)) 1)
        (else (+ (count-leaf (car tree))
                 (count-leaf (cdr tree))))))

(count-leaf '(1 2 (3 4) 5)) => 5

上の定義では、tree の値が、nil のときと、not pair つまり値がコンスセルではないときつまり葉の値のときという二つの終了条件があるが、これは葉の一つ手前の節のコンスセルの car の部分が数値にリンクし、cdr の部分が nil にリンクしていることがあるからだ。これを考慮に入れると上のプログラムも、

1.終了条件が 数値 か nil
2. ある節についてその節での値は右側の枝の数値と左側の枝の数値の和である。

という再帰的な定義を忠実にプログラムにしているだけだということがわかる。再帰的な方法でプログラムをするときは、終了条件と、ある一つの部分の構造を記述するだけでプログラムが実行されてしまうのだ。この「終了条件+まだ分かっていない部分を分かっているつもりで利用して計算する」というコツがわかると、驚くほど簡潔に実際に動作するプログラムを書くことができる。

したがって、上の木構造のデータをリストに変更するプログラムも次のように簡単に書くことができる。

(define (enumerate tree)
  (cond ((null? tree) tree)
        ((not (pair? tree)) (list tree))
        (else (append (enumerate (car tree))
                 (enumerate (cdr tree))))))

(enumerate '(1 2 (3 4) 5)) => (list 1 2 3 4 5)

このプログラムも

1.終了条件で値が空リストならそのまま、値が数値ならそれを使ったリストを作る。
2. ある節で右の枝のリストと左の枝のリストを連結する。

という「終了条件+わかったつもりでプログラム」の原則を守っていることがわかる。

わかりづらい再帰関数だが、「終了条件を決める」。「ある一点をとりあげて値がわかったつもりでプログラムを書く」という二つの条件だけに気をつけておけばわりに簡単にプログラムを発見することができる。さらに、そうして作ったプログラムは簡潔で応用範囲の広いものになる。これがわかると、面倒くさがり屋は何かあると、まず再帰でできないかと考えるようになってしまう。

どうしてこういうことができるかというと、木構造の任意の節について、葉の部分を含めて再帰的定義でカバーできるからだ。言いかえると、木構造のどの節をとりあげても再帰的定義の条件を満たしているのだ。木構造の様々なバリエーションにもかかわらず、その節はすべて再帰的定義の条件を満たしている。そのため、関数の微分と境界値から関数を求めるときのように局所的な性質から、大域的なふるまいを計算することができる。

木構造のどの節についても共通する性質を発見するという抽象化のおかげで、複雑な構造をもった多様な木を処理するプログラムを数行のプログラムで書いてしまうことができる。「抽象化というのは多様な表現の中に潜む共通な性質を発見することだ」というのがよくわかる例だ。

関数言語の分かりにくさは、この「抽象化」という概念操作がふんだんに表れるせいだが、一方では、そのことが複雑なデータの処理が数行のプログラムで書けてしまうという魔法のような能力を発揮する基ともなっているのだ。
by tnomura9 | 2008-03-11 02:10 | 考えるということ | Comments(0)
<< 視点をずらす 思考力 >>