Exercise 3.57. How many additions are performed when we compute the nth 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 section 3.5.1.
使用流产生的 fibs 如下：
(define fibs
(cons-stream 0
(cons-stream 1
(add-streams (stream-cdr fibs)
fibs))))
在之前的课本中我们已经看到，这个流的过程是
1 1 2 3 5 8 13 21 ... = (stream-cdr fibs)
0 1 1 2 3 5 8 13 ... = fibs
0 1 1 2 3 5 8 13 21 34 ... = fibs
计算出第 n 个 fibonacci 数的时候，总共只计算了 n - 2 次加法。
指数倍增加的 fibonacci
当我们没有对 delay 进行优化，那么每一次 cons-stream 实际只是把表达式放到 lambda 中保存起来，每一次求 fibonacci n 的时候，add-stream 中的两个参数都必须进行 n - 1 次加法求出第 n - 1 个 fibonacci 值。
与纯粹使用递归 f(n) = f(n-1) + f(n-2) 无异，是树形递归，在第 1.2 章中我们看到过这样的递归。