递归和循环及斐波那契数列
对于需要重复多次计算相同的问题，通常可以选择用递归或者循环两种方法。
- 递归是在一个函数内部调用这个函数自身。
- 循环是通过设置计算的初始值及终止条件，在一个范围内重复运算。
递归要比代码简洁且容易实现，一般优先选择递归方法。但是需要注意的是，递归由于是函数调用自身，而函数调用是有时间和空间的消耗的，每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址及临时变量，而往栈里压入数据和弹出数据都需要时间，因而递归实现的效率不如循环。
用递归和循环求1+2+…+n
int AddFrom1ToN_Recursive(int n)
{
return n <= 0 ? 0 : n + AddFrom1ToN_Recursive(n - 1)
}
int AddFrom1ToN_Iterative(int n)
{
int result = 0;
for(int i = 1; i <= n; ++i)
result += i;
return result;
}
斐波那契数列
斐波那契数列的表示：
f(0) = 0
f(1) = 1
f(n) = f(n-1)+f(n-2)
方法1：递归
long long Fibonacci_Solution1(unsigned int n)
{
if(n <= 0)
return 0;
if(n == 1)
return 1;
return Fibonacci_Solution1(n - 1) + Fibonacci_Solution1(n - 2);
}
该程序虽然采用了递归的方法，但是运行效率极低，代码中调用fib(N-1)的时候实际上同时计算了fib(N-2)。这种小的重复计算在递归过程中就会产生巨大的运行时间。
方法2：循环
long long Fibonacci_Solution2(unsigned n) { int result[2] = {0, 1}; if(n < 2) return result[n]; long long fibNMinusOne = 1; long long fibNMinusTwo = 0; long long fibN = 0; for(unsigned int i = 2; i <= n; ++ i) { fibN = fibNMinusOne + fibNMinusTwo; fibNMinusTwo = fibNMinusOne; fibNMinusOne = fibN; } return fibN; }
该算法是从下往上计算，首先根据f(0)和f(2)算出f(2),再根据f(1)和f(2)算出f(3)……依次类推就可以算出第n项了。时间复杂度为O(n)。
斐波那契数列的应用
有一段楼梯有10级台阶,规定每一步只能跨一级或两级,要登上第n级台阶有几种不同的走法?
问题分析：
首先考虑最简单的情况。如果只有1级台阶，显示只有一种跳法。如果有2级台阶，就有两种跳的方法：一种是分两次跳，每次跳1级；另一种是一次跳2级。
把n级台阶是的跳法看成是n的函数f(n)。当n>2时，第一次跳的时候有两种不同的选择：一是第一次只跳一级，此时跳法数等于剩下的n-1级台阶的跳法数，即f(n-1);另外一种是第一次跳2级，此时跳法数等于后面剩下的n-2级台阶的跳法数，即f(n-2)。因此n级台阶的不同跳法总数为f(n)=f(n-1)+f(n-2)。实际上就是求斐波那契数列。
版权声明：本文为zhangzijian原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。