Exercise 3.57 · 习题

Exercise 3.57: How many additions are performed
when we compute the n

th Fibonacci number using the definition of

fibs based on the add-streams procedure? Show that the number of

additions would be exponentially greater if we had implemented (delay ⟨exp⟩)

simply as (lambda () ⟨exp⟩), without using the

optimization provided by the memo-proc procedure described in

3.5.1.

练习 3.57：用基于 add-streams 过程定义的 fibs 计算第 n 个 Fibonacci 数时，共执行了多少次加法？请说明，如果我们将 (delay ⟨exp⟩) 简单地实现为 (lambda () ⟨exp⟩) 而不使用 3.5.1 节中 memo-proc 过程提供的优化，加法次数将呈指数级增长。