问题描述

斐波那契数列的性能优化 10C

http://www.nowcoder.com/books/coding-interviews/c6c7742f5ba7442aada113136ddea0c3?rp=1

牛客网上 的这道题，一个简单的递归，性能不满足要求，请问 有什么提高性能的算法

解决方案

递归性能当然差了，解决档案是:将递归改为迭代！

解决方案二：
为啥不直接上通项公式

解决方案三：

这是我写的源代码。接下来我将对递归和迭代进行分析，我觉得这才是重点！

解决方案四：
在大部分情况下，递归和迭代可以相互转化。递归的好处是程序简单明了，易于理解；缺点是效率低，为什么呢？因为递归过程中存在着大量的重复计算，举例说明：在计算F(5)时，程序要递归计算F(3)和F(4)，而在计算F(4)时，又要递归计算F(2)和F(3)，有没有发现在计算F(4)时又重复计算了一次
F(3)。这种情况在递归过程中是很多的，为了便于理解，给出计算F(4)的递归调用流程图，你可以发现n取值越大，重复计算的越多：

解决方案五：
而对于迭代，不存在重复计算的问题，迭代的思想是：为了计算第n项，依次将前面n项（从第0项开始）求出并保存起来，计算每一项是直接调用保存的值，即它前面的两项值。