Exercise 5.26. Use the monitored stack to explore the tail-recursive property of the evaluator (section 5.4.2). Start the evaluator and define the iterative factorial procedure from section 1.2.1:
(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter (* counter product)
(+ counter 1))))
(iter 1 1))
Run the procedure with some small values of n. Record the maximum stack depth and the number of pushes required to compute n! for each of these values.
a. You will find that the maximum depth required to evaluate n! is independent of n. What is that depth?
b. Determine from your data a formula in terms of n for the total number of push operations used in evaluating n! for any n > 1. Note that the number of operations used is a linear function of n and is thus determined by two constants.
a
我们选择下列 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 1)
(total-pushes = 64 maximum-depth = 10)
;;; EC-Eval value:
1
;;; EC-Eval input:
(factorial 2)
(total-pushes = 99 maximum-depth = 10)
;;; EC-Eval value:
2
;;; 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 10)
(total-pushes = 379 maximum-depth = 10)
;;; EC-Eval value:
3628800
;;; EC-Eval input:
maximum-depth 都是 10 。
b
简单列式就可以得出
a + b = 64
2a + b = 99
a = 35
b = 29
关于 n 的函数是