1.2.2 木構造再帰

文責:@ayato_p

計算でよくあるパターンの一つとして, 木構造再帰 (tree recursion) がある. ここでは木構造再帰の例として Fibonacchi 数を取り扱う. Fibonacchi 数の定義は次の通り.

\[\begin{split}\begin{eqnarray} Fib(n) = \left\{ \begin{array}{3} 0 & n = 0 \\ 1 & n = 1 \\ Fib(n - 1) + Fib(n - 2) & その他 \end{array} \right. \end{eqnarray}\end{split}\]

これを再帰的手続きの定義へと翻訳する.

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

この計算パターンを考えたとき, (fib 5) を計算するには (fib 4)(fib 3) を計算することが分かる. さらに (fib 4) を計算するためには (fib 3)(fib 2) を計算する必要がある. 最終的には終端条件である n = 0 , n = 1 になるまで同様の計算を繰り返す. 手続き fib は呼び出される度に, 自分自身を二回呼び出すためプロセスは樹木状へと進化する.

手続きの葉である (fib 1)(fib 0) の演算回数が正確に Fib(n + 1) であるのを示すのは難しくありません. この方法の酷さを知るために Fib(n) の値が n に対して指数関数的に増加することを示すことが出来ます. Fib(n) は以下の条件の場合に \(\frac{\phi^n}{\sqrt5}\) に最も近い整数となる. ただし,

\[\phi = \frac{(1+\sqrt5)}{2} \approx 1.6180\]

黄金比 であり, 次の等式を満たします.

\[\phi^2 = \phi+1\]

従ってプロセスは入力に伴い, 指数関数的に増加するステップ数を要することが分かる. 一方で要求される記憶域は入力に対して, 線形にしか増加しません. 一般的に, 木構造再帰プロセスで必要なステップ数は木構造のノードの数に比例し, 必要な記憶域は木構造の最大深さに比例する.

Fibonacci 数の計算の反復的プロセスを形式化する場合, 二つの変数 a, bFib(1)=1, Fib(0)=0 で初期化し,

\[\begin{split}\begin{array}{l} a & \leftarrow a + b\\ b & \leftarrow a \end{array}\end{split}\]

の同時の変換を繰り返すことによって表現する. 従って Fibonacci 数を反復的に以下の手続きを用いて計算することが可能です.

(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

この Fib(n) を計算する二つ目の方法は線形反復です. 二つの方法により要求されるステップ数の差は入力が小さくても非常に大きくなります. だからといって木構造再帰プロセスが役に立たないというわけではなく, 階層構造のデータを操作するプロセスを考えた場合などは自然で強力なツールです.

例: 両替の計算

次の問題を考える. 50 セント, 25 セント, 10 セント, 5 セント, 1セントがあるとして 1 ドルの両替にはどのくらいの場合があるか. つまり, 金額に対して両替の場合の数を計算する手続きは書けるか.

n 種類の硬貨を使う, 金額 a の両替の場合の数は

  • 最初の種類の硬貨以外を使う, 金額 a の両替の場合の数
  • d を最初の硬貨の額面金額 [denomination] として, n 種類の硬貨を使う, 金額 a-d の両替の場合の数

この方法は両替が最初の硬貨を使わないのと, 使うのの二つのグループに分けることで問題を解決する. 少ない種類の硬貨を使う少ない金額の問題へ再帰的に縮小させることが出来る.

  • a がちょうど 0 なら, 両替の場合の数は 1
  • a が 0 より少なければ, 両替の場合の数は 0
  • n が 0 なら, 両替の場合の数は 0

この記述を再帰的手続きへと翻訳する.

(define (count-change amount)
  (cc amount 5))

(define (cc amount kinds-of-conins)
  (cond
   ((zero? amount) 1)
   ((or (< amount 0)(zero? kinds-of-conins)) 0)
   (else
    (+ (cc amount (- kinds-of-conins 1))
       (cc (- amount (first-denomination kinds-of-conins))
        kinds-of-conins)))))

(define (first-denomination kinds-of-conins)
  (cond
   ((= kinds-of-conins 1) 1)
   ((= kinds-of-conins 2) 5)
   ((= kinds-of-conins 3) 10)
   ((= kinds-of-conins 4) 25)
   ((= kinds-of-conins 5) 50)))

1 ドルの両替をつくる場合のプロセスの動きを調べるのに少し大きすぎるので, 10 セントの両替をつくる場合のプロセスの動きを確認する.

(count-change 10)

(cc 10 5) -> (cc -40 5) -> 0
|
(cc 10 4) -> (cc -15 4) -> 0
|
(cc 10 3) -> (cc 0 3) -> 1
|
(cc 10 2) -> (cc 5 2) -> (cc 0 2) -> 1
|            |
|            (cc 5 1) -> ... -> (cc 0 1) -> 1
|            |
|            (cc 5 0) -> 0
|
(cc 10 1) -> ... -> (cc 0 1) -> 1
|
(cc 10 0) -> 0

このように木構造的再帰プロセスを生成することが確認出来る. fib 関数と同様にステップ数が指数関数的に増えるが, この冗長な計算に対処する一つの方法は メモ化 (memoization) として知られている.

Table Of Contents

Previous topic

1.2.1 線形再帰と反復

Next topic

1.2.3 増加の程度