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と推定できる.