文責: | @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 に比例して成長するのるため, このようなプロセスを特に 線形反復的プロセス という.
手続きの定義がその手続き自身を指す構文上の事実. プロセスが再帰的, 反復的のいずれにしても構文上再帰的な手続きであれば, それは再帰的手続きである.