【scheme】1.2.1＠SICP 再帰と反復と遅延演算

大晦日なのに、またまた階乗計算ですが。線形再帰と反復。 お陰で遅延評価（遅延演算）がわかったー！計算式の評価の前に式展開が先に行われるということなんだねと思う。以下、SICPよりほぼ写経ですが・・・。 一般的な階乗計算関数

;;factorial ;;n! = n * (n - 1) * (n - 2)....3 * 2 * 1 (define factorial   (lambda (n)     (if (zero? n)       1       (* n (factorial (- n 1)))))) (factorial 5);;=> 120

上記関数の実行イメージ

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

こっちの発想はなかった。 1*2*3・・・とやっていって、かける数がパラメータで与えられた回数に達するまで続ける方法。

;;n! = 1 * 2 * 3.... (define factorial2   (lambda (n)     (define iter       (lambda (product counter)         (if (> counter n)           product           (iter (* counter product) (+ counter 1)))))     (iter 1 1))) (factorial2 5);;=> 120

実行イメージ

(factorial2 5) (iter 1 1 5) (iter 1 2 5) (iter 2 3 5) (iter 6 4 5) (iter 24 5 5) (iter 120 6 5) 120