练习3-57

原文

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 ) simply as (lambda () ), without using the optimization provided by the memo-proc procedure described in section 3.5.1.

分析

斐波那契中每个数都会由前两个数计算而来。因此斐波那契数列要求每一次求和时对空间的需求没有增加。当回头调用前面计算过的斐波那契数时不必重新计算。因为没有计算的是从0和1开始的，因此计算fib(n)至少需要fib(n)-1次加法。