問題5.27

問題5.27 – SICP（計算機プログラムの構造と解釈）その277

2009年11月16日

再帰的 factorial でのスタックの最大深さとプッシュ総数を調べる。

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

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

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

(total-pushes = 80 maximum-depth = 18)
;;; EC-Eval value:
6

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

(total-pushes = 112 maximum-depth = 23)
;;; EC-Eval value:
24

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

(total-pushes = 144 maximum-depth = 28)
;;; EC-Eval value:
120

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

(total-pushes = 176 maximum-depth = 33)
;;; EC-Eval value:
720

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

(total-pushes = 208 maximum-depth = 38)
;;; EC-Eval value:
5040

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

(total-pushes = 240 maximum-depth = 43)
;;; EC-Eval value:
40320

n	total-pushes	maximum-depth
3	80	18
4	112	23
5	144	28
6	176	33
7	208	38
8	240	43

T = (32 * n) - 16
D = (5 * n) + 3

実験の総括

	最大深さ	プッシュ回数
再帰的階乗	`(5 * n) + 3`	`(32 * n) - 16`
反復的階乗	`10`	`(35 * n) + 29`

計算機プログラムの構造と解釈

posted with amazlet at 08.11.07

ジェラルド・ジェイサスマンジュリーサスマンハロルドエイブルソン
ピアソンエデュケーション
売り上げランキング: 6542

Amazon.co.jp で詳細を見る