递归算法---斐波那契数列（二）

斐波那契数列（Fibonacci sequence）又称为“黄金分割”数列，因数学家列昂纳多·斐波那契以兔子繁殖为例引入，故又称为兔子数列。

兔子数列描述：如果兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子，假设所有的兔子都不死，那么一年后可以繁殖多少对兔子呢？

思路分析：我们拿新出生的一对小兔子分析一下，第一个月小兔子没有繁殖能力，所以还是一对；两个月后，生下一对小兔子，此时有共有2对；三个月后，老兔子又生下一对，因为前一对小兔子还没有繁殖能力，所以此时共3对小兔子。。。。。依次类推，可以列出下表：

image.png

繁殖过程如下图所示：

image.png

可以发现：1号小兔子经过6个月就变成了8对小兔子相邻两项之和，构成了后一项

用我们学过的数列可以表示为：

image.png

我们用程序实现这样的数列有两种方法，一种是迭代法一种是递归法
【假设我们需要打印出前10位的斐波那契数列，代码该如何编写呢？？？】

第一种：迭代法

#include <iostream>
using namespace std;
int fibonacci_iteration(int n){
    int i;
    int a[n];
    if (sizeof(a)==1) {
        a[0] = 0;
        cout<<a[0]<<"、";
    }else{
        a[0] = 0;
        cout<<a[0]<<"、";
        a[1] = 1;
        cout<<a[1]<<"、";
    }
    for(i = 2;i<n;i++){
        a[i]=a[i-1]+a[i-2];
        cout<<a[i]<<"、";
    }
    return 0;
}

int main(int argc, const char * argv[]) {
    fibonacci_iteration(10);
    return 0;
}

返回结果：0、1、1、2、3、5、8、13、21、34

第一种：递归法

using namespace std;
int fibonacci_recursion(int n){
    if (n < 2) {
        return n == 0 ? 0 : 1;
    }
    return fibonacci_recursion(n-1)+fibonacci_recursion(n-2);
}
int main(int argc, const char * argv[]) {
    for (int i=0; i<10; i++) {
        printf("%d、",fibonacci_recursion(i));
    }
    return 0;
}

返回结果：0、1、1、2、3、5、8、13、21、34

在高级语言中，调用自己和调用其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，成为递归函数
⚠️写递归程序最怕的就是陷入永不结束的无限递归中，所以：每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出

迭代和递归的比较：
1、递归使用的是选择结构   迭代使用的是循环结构       
2、递归能使程序的结构更清晰、更简洁、更容易让人理解，但是大量的递归调用会建立函数的副本，会消耗大量的时间和内存；
   迭代则不需要反复建立函数副本和占用额外的内存