Serendip

Web Studio

問題5.26

反復的手続きの factorial を使った各値の n! の計算に使うスタックの最大深さとプッシュの回数の結果。

;;; 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 3)

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

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

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

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

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

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

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

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

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

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

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

a. n に無関係な最大深さとは何か

最大深さは n に関係無く 10 となった。
これは末尾再帰されて、スタックへの退避を行なわずに eval-dispatch へ行くためにスタック使用量が一定以上増加しないため。

b. n! に使ったプッシュ演算の総数の n に関する式

T = (35 * n) + 29

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

posted with amazlet at 08.11.07

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

Amazon.co.jp で詳細を見る