Exercise 5.26 · 习题

Exercise 5.26: Use the monitored stack to
explore the tail-recursive property of the evaluator (5.4.2).
Start the evaluator and define the iterative factorial procedure from
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.

You will find that the maximum depth required to evaluate n
! is independent
of n. What is that depth?

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.

练习 5.26：利用带监控的栈探究求值器的尾递归特性（5.4.2 节）。启动求值器，定义 1.2.1 节的迭代型阶乘过程：

(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter (* counter product)
(+ counter 1))))
(iter 1 1))

用若干较小的 n 值运行该过程，记录计算 n! 时的最大栈深度和压栈次数。

你会发现，计算 n! 所需的最大深度与 n 无关。这个深度是多少？

根据数据，确定计算任意 n ≥ 1 的 n! 时所用总压栈操作次数关于 n 的公式。注意，操作次数是 n 的线性函数，因此由两个常数确定。