Exercise 5.14: Measure the number of pushes and
the maximum stack depth required to compute n
! for various small values of
n using the factorial machine shown in Figure 5.11. From your data
determine formulas in terms of n for the total number of push operations
and the maximum stack depth used in computing n
! for any n
>
1. Note
that each of these is a linear function of n and is thus determined by two
constants. In order to get the statistics printed, you will have to augment
the factorial machine with instructions to initialize the stack and print the
statistics. You may want to also modify the machine so that it repeatedly
reads a value for n, computes the factorial, and prints the result (as we
did for the GCD machine in Figure 5.4), so that you will not
have to repeatedly invoke get-register-contents,
set-register-contents!, and start.
练习 5.14：使用图 5.11 所示的阶乘机器，测量计算若干个较小 n 值的 n! 所需的压栈次数和最大栈深度。根据所得数据，分别确定计算任意 n > 1 的 n! 时，总压栈操作次数和最大栈深度关于 n 的公式。注意，两者均为 n 的线性函数，因此各由两个常数确定。为了打印统计信息，你需要向阶乘机器增加用于初始化栈并打印统计数据的指令。你可能还希望修改机器，使其反复读入 n 的值、计算阶乘并打印结果（如我们在图 5.4 中对 GCD 机器所做的那样），从而避免每次都需要反复调用 get-register-contents、set-register-contents! 和 start。