阿狗工具

什么是递归算法？
若一个算法直接的或间接的调用自己本身，则称这个算法是递归算法。递归本质上也是一种循环的算法结构，它把较复杂的计算逐次归结为较简单的情形的计算，直到归结到最简单情形的计算，并最终得到计算结果为止。

递归算法的特性
例如，我们现在要求n!那么这个问题就可以转化成求n(n-1),而我们要求(n-1)!又可以转化成求(n-1)(n-2)，有规律的递减，直到1！然后结束。递归算法的执行过程划分为递推和回归两个阶段。在递推阶段，把规模为n的问题的求解推到比原问题的规模较小的问题求解，且必须要有终止递归的条件。在回归阶段，当获得最简单情况的解后，逐级返回，依次得到规模较大问题的解。

示意图.png

（1）求解规模为n的问题可以转化为一个或多个结构相同、规模较小的问题，然后从这些小问题的解能方便地构造出大问题的解。
（2）递归调用的次数必须是有限的。
（3）必须有结束递归的条件（边界条件）来终止递归。

斐波那契数列问题

1.问题描述

著名的数列—斐波那契数列（Fibonacci），可以定义为：

当n = 0时；F(n) = 0。（从实际意义出发，不考虑n<0的情况）

当n = 1时；F(n) = 1。

当n > 1时；F(n) = F(n-1)+F(n-2)。

兔子.png

请求出第n项斐波那契数，以及前n项斐波那契数列的和（在没有兔子死亡的理想情况下）。

2.分析

从上面的规律我们可以得到一个无穷数列（1，1，2，3，5，8，13，21，34，55……），求解第n个斐波那契数，必须先计算F(n-1)和F(n-2)，而计算F(n-1)和F(n-2)又必须先计算F(n-3)和F(n-4)，以此类推，直至F(1)和F(2)，而F(1)和F(2)是可以立即求得，因此该问题可以利用递归方法求解。

3.程序运行

#include<iostream>
using namespace std;

int fib(int n){
    int f=0;
    if(n==1||n==2) return 1;    //第一个月兔子没有成熟，不出生新兔子，第二个月成熟了，只有一对成熟兔子,
                                //我们也可以这么写：if（n<=1）return n;
    f=fib(n-1)+fib(n-2);        //n>=3时，当月兔子数等于前一个月兔子数目加上上月兔子数
    return f;
}

int main(){
    int n,i,m=0;
    cin>>n;
    m=fib(n);
    cout<<"第"<<n<<"项是"<<m<<endl;
    m=0;
    for(i=1;i<=n;i++) m=fib(i)+m;
    cout<<"前"<<n<<"项和是"<<m<<endl;
    return 0;
}

至此我们已经能求出第n项斐波那契数，以及前n项斐波那契数列的和了。