递归，就是自己调用自己。迭代，其实可以简单理解成循环。很多问题都可以用这两种方式来解决。这篇博客来解决一个问题，求斐波那契数列的第n项，也就是第n个斐波那契数。
斐波那契数列指的是前两项是1，从第三项开始每一项等于前两项之和。也就是1,1,2,3,5,8，...
用递归的思路来想，求第n个斐波那契数其实就可以转换成求第n-1个斐波那契数和第n-2个斐波那契数。准确来说，从第三个斐波那契数之后都是这么求，而前两个就不用求了，直接返回1即可，而这就是递归的限制条件。把这个想法转化成代码如下
#includeint Fib(int n) { if (n < 3) { return 1; } else { return Fib(n - 1) + Fib(n - 2); } } int main() { int n = 0; scanf("%d", &n); int ret = Fib(n); printf("%dn", ret); return 0; }
但是，这个问题用递归来解决是具有严重的缺陷的。因为，假设我们要求的数比较大，每次调用这个函数都要把这个数前面两个数作为参数再调用两次，那么调用的次数是以指数级别增长的，比方说我们要求Fib(50),就要求Fib(49)和Fib(48),要求Fib(49),就要求Fib(48)和Fib(47)，要求Fib(48),就要求Fib(47)和Fib(46)...以此类推，最终的数量级是接近2的50次方！这可是一个天文数字！所以，这个问题不建议使用递归来实现。
既然递归不行，我们就只能老老实实使用循环来解决这个问题。我们可以创建三个变量，a,b,c，每次把a+b赋值给c，这样就能不断往后算，每次算完后再求b+c，具体方法就是把b赋值给a，然后把c赋值给b，再求a+b即可，此时算出来的值就是下一个斐波那契数。还有一个问题，由于要反复计算a+b，所以需要使用循环，那么循环的条件是什么呢？或者说，要循环几次？第三个斐波那契数只用计算一次，所以第n个数需要循环n-2次。循环结束后直接返回c即可。由于前两个斐波那契数不需要进入循环就返回了，而直接返回的是变量c，所以一开始就把c初始化成1就能够处理掉这种特殊情况。完整的代码如下：
#includeint Fib(int n) { int a = 1; int b = 1; int c = 1; while (n>2) { c = a + b; a = b; b = c; n--; } return c; } int main() { int n = 0; scanf("%d", &n); int ret = Fib(n); printf("%dn", ret); return 0; }
既然递归和迭代都能够解决很多问题，那么什么时候使用递归，什么时候使用迭代？很简单，如果递归的实现很好想并且代码没有什么比较大的缺陷时就使用递归，如果递归代码不太好想或者虽然很好想但是存在较大的缺陷（如上面的求第n个斐波那契数的递归代码），哪怕迭代的代码再难想也要硬着头皮写出来。
补充一下，经典的青蛙跳台阶问题其实也跟斐波那契数列问题很类似。所谓青蛙跳台阶，就是一只青蛙在台阶底部往上跳，假设有n个台阶，青蛙一次只能跳1个或2个台阶，请问跳上去有几种跳法？
这个问题非常简单。假设跳n个台阶的跳法数是f(n)，那么就分类讨论：如果第一次跳1个台阶，剩下n-1个台阶的跳法数是f（n-1），如果第一次跳2个台阶，剩下n-2个台阶的跳法数就是f（n-2），也就是说，f（n）=f（n-1）+f（n-2）。这不就是斐波那契数列吗！而很容易得出，f（1）=1，f（2）=2，所以这个数列就是1,2,3,5,8，...所以这个数列的第n项就是斐波那契数列的第n+1项，也就是说，只需要把n+1传给上面讲解斐波那契数列写的代码的fib函数中即可。
