1.2.1 線形再帰と反復

文責:@ayato_p
n! = n・(n-1)・(n-2)・・・3・2・1

で定義される階乗関数を考える.

再帰的プロセス

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

上記の手続き factorial は, 置き換えモデルによって以下のような膨張と, それに続く収縮の形をとる.

(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 1))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720

膨張は 遅延演算 の列を作るときに起きている. 再帰的プロセスの実行では,処理系が後に実行する演算を記憶しておく必要がある. 遅延演算の列の長さが n に比例して成長するため, このようなプロセスを特に 線形再帰的プロセス という.

反復的プロセス

(define (factorial n)
  (fact-iter 1 1 n))
(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))

反復的プロセスとして定義した関数 factorial は, 再帰的プロセスで定義した factorial 関数のように伸び縮みしない形をとる.

(factorial 6)
(fact-iter   1 1 6)
(fact-iter   1 2 6)
(fact-iter   2 3 6)
(fact-iter   6 4 6)
(fact-iter  24 5 6)
(fact-iter 120 6 6)
(fact-iter 720 7 6)
720

反復的プロセスの状態は, その状態が一定個数の 状態変数 と, 状態が移った時, 状態変数をどう更新するかの一定した規則と, プロセスを停止させる条件を規定する終了テストで総括される. 必要なステップ数が n に比例して成長するのるため, このようなプロセスを特に 線形反復的プロセス という.

再帰的手続き

手続きの定義がその手続き自身を指す構文上の事実. プロセスが再帰的, 反復的のいずれにしても構文上再帰的な手続きであれば, それは再帰的手続きである.

Table Of Contents

Previous topic

1.2 手続きとその生成するプロセス

Next topic

1.2.2 木構造再帰