Exercise 5.46 · 习题

Exercise 5.46: Carry out an analysis like the
one in Exercise 5.45 to determine the effectiveness of compiling the
tree-recursive Fibonacci procedure

(define (fib n)
(if ( n 2)
n
(+ (fib (- n 1)) (fib (- n 2)))))

compared to the effectiveness of using the special-purpose Fibonacci machine of

Figure 5.12. (For measurement of the interpreted performance, see

Exercise 5.29.) For Fibonacci, the time resource used is not linear in

n

; hence the ratios of stack operations will not approach a limiting value

that is independent of n.

练习 5.46：仿照练习 5.45 的分析方法，确定编译树形递归 Fibonacci 过程

(define (fib n)
(if ( n 2)
n
(+ (fib (- n 1)) (fib (- n 2)))))

相对于使用图 5.12 专用 Fibonacci 机器的效率差异。（关于解释执行的性能测量，参见练习 5.29。）对于 Fibonacci，所用时间资源不与 n 成线性关系，因此栈操作次数之比不会趋近于与 n 无关的极限值。