1.2.1 Linear Recursion and Iteration

SICP

n!でいろいろみてみよう

置き換えモデルだと山型のスタック

見方を変えてみよう.
これまでの計算結果を保持してみると...

(define (factorial n)
  (fact-iter (1 1 n))

(definie (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* product counter)
                   (+ counter 1)
                   (max-count))))

とすると、展開してもただのループになるので、記憶しておく量がすくなくて済む.

比較

  1. 置き換えモデルは山形に展開、収縮する
    • なぜこんなことがおきるかというと、実行が「遅らされる」から
    • 再帰プロセスという名前.
    • インタプリタ側でスタックを保持しておく必要がある.
  2. 2つめのやつは収縮/膨張しない
    • プログラム側で実行経過を保持
    • 反復プロセスという名前
    • 状態変数を保持している
    • 実行に伴い状態変数が変化していき、これがトリガとなって実行が終了
    • 状態数nに比例する場合「線形反復プロセス」という

もっと違う見方で比較

  1. 反復プロセス
    • 全てのポイントでプロセスの状態をプログラム側で保持
    • プログラムが途中でとまったらとしたら、保持している値を代入してあげればそこから再実行可能
  2. 再帰プロセス
    • インタプリタが保持している隠れパラメータを復元する必要アリ
    • 遅延が長くなればなるほど保持すべき情報は大きくなる

注意

  1. 再帰プロセスと再帰関数は異なる
    • 再帰関数は、自分自身を直接的、間接的に呼び出している関数のこと
    • 再帰プロセスは、実行過程がどのように変化していくかによって分類

混乱の原因

  • Cなどの実装では、反復プロセスでも再帰プロセスでも関数が実行されるとメモリを食う(ホント？)
  • 反復プロセスはループ構文を使ってのみ表現可能

Exercise 1.9

(define (+ a b) 
  (if (= a 0) 
      b 
      (inc (+ (dec a) b)))) 
(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5))
(inc (inc (inc (+ 1 5)))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc (5)))))
(inc (inc (inc (6))))
(inc (inc (7)))
(inc (8))
(9)
9

(define (+ a b) 
  (if (= a 0) 
      b
      (+ (dec a) (inc b)))) 
(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9

Excersice 1.10

gosh> (define (A x y) 
(cond ((= y 0) 0) 
((= x 0) (* 2 y)) 
((= y 1) 2) 
(else (A (- x 1) 
(A x (- y 1)))))) 
A
gosh> (A 1 10)
1024
gosh> (A 2 4)
65536
gosh> (A 3 3)
65536

(define (f n) (A 0 n)) 
=> f(n) =  2n
(define (g n) (A 1 n)) 
=> g(n) = 
(define (A x y) 
  (cond ((= y 0) 0) 
        ((= x 0) (* 2 y)) 
        ((= y 1) 2) 
        (else (A (- x 1) 
                 (A x (- y 1)))))) 

(A 1 3)
(A 0 (A 1 2))
(A 0 (A 0 (A 1 1)))
(A 0 (A 0 (2)))
(A 0 (4))
(8)
8

2^n



(define (h n) (A 2 n))
(define (A x y) 
  (cond ((= y 0) 0) 
        ((= x 0) (* 2 y)) 
        ((= y 1) 2) 
        (else (A (- x 1) 
                 (A x (- y 1)))))) 

gosh> (h 1)
2
gosh> (h 2)
4
gosh> (h 3)
16
gosh> (h 4)
65536

(2n)^2n