SICP 問題 5.26

監視つきスタックを使い，評価器の末尾再帰的特性を検討する．

;;; EC-Eval input:
(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))

(total-pushes = 3 maximum-depth = 3)
;;; EC-Eval input:
(factorial 0)

(total-pushes = 34 maximum-depth = 8)
;;; EC-Eval value:
1

;;; EC-Eval value:
ok

;;; EC-Eval input:
(factorial 1)

(total-pushes = 69 maximum-depth = 10)
;;; EC-Eval value:
1

;;; EC-Eval input:
(factorial 2)

(total-pushes = 104 maximum-depth = 10)
;;; EC-Eval value:
2

;;; EC-Eval input:
(factorial 3)

(total-pushes = 139 maximum-depth = 10)
;;; EC-Eval value:
6

;;; EC-Eval input:
(factorial 4)

(total-pushes = 174 maximum-depth = 10)
;;; EC-Eval value:
24

;;; EC-Eval input:
(factorial 5)

(total-pushes = 209 maximum-depth = 10)
;;; EC-Eval value:
120

;;; EC-Eval input:
(factorial 6)

(total-pushes = 244 maximum-depth = 10)
;;; EC-Eval value:
720

;;; EC-Eval input:
(factorial 7)

(total-pushes = 279 maximum-depth = 10)
;;; EC-Eval value:
5040

;;; EC-Eval input:
(factorial 8)

(total-pushes = 314 maximum-depth = 10)
;;; EC-Eval value:
40320

;;; EC-Eval input:
(factorial 9)

(total-pushes = 349 maximum-depth = 10)
;;; EC-Eval value:
362880

;;; EC-Eval input:
(factorial 10)

(total-pushes = 384 maximum-depth = 10)
;;; EC-Eval value:
3628800

この末尾再帰階乗計算のプッシュ回数は35n+34，最大深さは10と推定できる．