斐波那契数列求第N项递归改进

本文主要是介绍斐波那契数列求第N项递归改进，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

递归思路：

int fib(int n) {if ( 2 > n) {return n;}return fib(n-1) + fib(n-2);
}

展开递归计算过程，如下为求第fib(5)的递归过程。

如上发现好多重复计算过程，时间与空间的消耗也是必然的。
颠倒计算方向，由自顶而下递归，为自底而上迭代（动态规划）

算法描述为：

int fib(int n) {int f = 0, g = 1;while( --n > 0 ) {g = g + f;f = g - f;}return g;
}

这篇关于斐波那契数列求第N项递归改进的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---