Exercise 5.27 · 习题

Exercise 5.27: For comparison with Exercise 5.26,
explore the behavior of the following procedure for computing factorials
recursively:

(define (factorial n)
(if (= n 1)
1
(* (factorial (- n 1)) n)))

By running this procedure with the monitored stack, determine, as a function of
n, the maximum depth of the stack and the total number of pushes used in
evaluating n
! for n
≥
1. (Again, these functions will be linear.)
Summarize your experiments by filling in the following table with the
appropriate expressions in terms of n:
Maximum

Number of

depth

pushes

Recursive

factorial

Iterative

factorial

The maximum depth is a measure of the amount of space used by the evaluator in

carrying out the computation, and the number of pushes correlates well with the

time required.

练习 5.27：为了与练习 5.26 对比，探究以下递归型阶乘过程的行为：

(define (factorial n)
(if (= n 1)
1
(* (factorial (- n 1)) n)))

利用带监控的栈运行该过程，确定计算 n ≥ 1 的 n! 时栈的最大深度和总压栈次数关于 n 的函数。（这两个函数同样是线性的。）用关于 n 的适当表达式填写下表，汇总你的实验结果：
最大深度　　压栈次数
递归型阶乘
迭代型阶乘
最大深度衡量求值器执行计算所用的空间量，压栈次数则与所需时间密切相关。