练习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次加法。

---

---

感谢访问，希望对您有所帮助。 欢迎关注或收藏、评论或点赞。

---

为使本文得到斧正和提问，转载请注明出处：

---

版权声明：本文为 NoMasp柯于旺 原创文章，如需转载请联系本人。