SICP演習問題5.26, 5.27, 5.28

3問続いているけれど，やることは同じなのでまとめてしまう．

5.26

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* product counter)
              (+ counter 1))))
  (iter 1 1))

を実行するときのスタックを監視せよという問題．
スタックの量はこのように表示される．

;; n = 5
(factorial 5)
;;; EC-Eval input:
(total-pushes = 204 maximum-depth = 10)

;;; EC-Eval value:
120

nが1~5を表にまとめる．

n	total-pushed	maximum-depth
5	204	10
4	169	10
3	134	10
2	99	10
1	64	10

maximum-depthが定数であることがわかる．
また，total-pushedは35n+29で表せるのでO(n)になる．(5.26のbの答え)

5.27

5.27では

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

のような再帰的プロセスを実行したときのスタックを監視せよという問題．
5.26と同様に表にまとめる．

n	total-pushed	maximum-depth
5	144	28
4	112	23
3	80	18
2	48	13
1	16	8

簡単な考察をすると，

• 計算時間(tatal-pushes)に関して, 数字だけ見てみると，反復的(35n+29) > 再帰的(16(2n-1))であるが，どちらもO(n)である
• メモリ容量(maximum-depth)に関しては，反復的なほうは定数(10)なのでO(1)であるのに対し，再帰的なほうは, 5n+3なのでのO(n)である

5.28

5.28では，評価器のev-sequenceを

ev-sequence
  (test (op no-more-exps?) (reg unev))
  (branch (label ev-sequence-end))
  (assign exp (op first-exp) (reg unev))
  (save unev)
  (save env)
  (assign continue (label ev-sequence-continue))
  (goto (label eval-dispatch))
ev-sequence-continue
  (restore env)
  (restore unev)
  (assign unev (op rest-exps) (reg unev))
  (goto (label ev-sequence))
ev-sequence-end
  (restore continue)
  (goto (reg continue))

として，評価器のなかに末尾再帰的でないものを組み込んだ場合にどうなるか，というもの．
それぞれ以下のようになる

• 反復的

n	total-pushed	maximum-depth
5	218	29
4	181	26
3	144	23
2	107	20
1	70	17

• 再帰的

n	total-pushed	maximum-depth
5	154	43
4	120	35
3	86	27
2	52	19
1	18	11

反復的プロセスが反復的でなくなってしまうことがわかる．