SICP 問題 5.28

ev-sequenceで行っていた末尾再帰の最適化をやめた場合のfactorialの比較．
最適化をやめると反復的factorialはプッシュ回数が37n+1, 最大深さが3n+11.
再帰的factorialはそれぞれ，34n-16, 8n+3となった．
末尾再帰の最適化がないと末尾再帰的に書いても最大深さが線形に成長する．
末尾再帰の最適化がある場合は 反復的factorial 35n+34, 10 再帰的factorial 32n-16, 5n+3.

;;; 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 value:
ok

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

(total-pushes = 38 maximum-depth = 14)
;;; EC-Eval value:
1

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

(total-pushes = 75 maximum-depth = 17)
;;; EC-Eval value:
1

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

(total-pushes = 112 maximum-depth = 20)
;;; EC-Eval value:
2

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

(total-pushes = 149 maximum-depth = 23)
;;; EC-Eval value:
6

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

(total-pushes = 186 maximum-depth = 26)
;;; EC-Eval value:
24

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

(total-pushes = 223 maximum-depth = 29)
;;; EC-Eval value:
120

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

(total-pushes = 260 maximum-depth = 32)
;;; EC-Eval value:
720

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

(total-pushes = 297 maximum-depth = 35)
;;; EC-Eval value:
5040

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

(total-pushes = 334 maximum-depth = 38)
;;; EC-Eval value:
40320

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

(total-pushes = 371 maximum-depth = 41)
;;; EC-Eval value:
362880

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

(total-pushes = 408 maximum-depth = 44)
;;; EC-Eval value:
3628800

;;; EC-Eval input:
(define (factorial-recur n)
  (if (= n 1)
      1
      (* (factorial-recur (- n 1)) n)))

(total-pushes = 3 maximum-depth = 3)
;;; EC-Eval value:
ok

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

(total-pushes = 18 maximum-depth = 11)
;;; EC-Eval value:
1

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

(total-pushes = 52 maximum-depth = 19)
;;; EC-Eval value:
2

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

(total-pushes = 86 maximum-depth = 27)
;;; EC-Eval value:
6

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

(total-pushes = 120 maximum-depth = 35)
;;; EC-Eval value:
24

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

(total-pushes = 154 maximum-depth = 43)
;;; EC-Eval value:
120

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

(total-pushes = 188 maximum-depth = 51)
;;; EC-Eval value:
720

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

(total-pushes = 222 maximum-depth = 59)
;;; EC-Eval value:
5040

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

(total-pushes = 256 maximum-depth = 67)
;;; EC-Eval value:
40320

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

(total-pushes = 290 maximum-depth = 75)
;;; EC-Eval value:
362880

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

(total-pushes = 324 maximum-depth = 83)
;;; EC-Eval value:
3628800