斐波拉契数列的递推递归求解算法

介绍：

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(3)=2,F(n)=F(n-1)+F(n-2)（n>=4，n∈N*）

递推=iterative；递归=recursive

递归指自我调用的函数；递推指重复进行的过程，这个重复的过程可以是，有自我调用的函数的重复的自我调用，也可以是其它过程。

1．裴波那契数列的递推求解算法。

#include<iostream>
using namespace std;
int Fib(int n){
    int f1=1,f2=1,i,f;
    if(n<=2)return 1;
    for(i=3;i<=n;i++){
        f=f1+f2;
        f1=f2;
    f2=f;
    }return f;
}
int main(){
  int n;
  cin>>n;
  for(int i=1;i<=n;i++){
    cout<<Fib(i)<<endl;
  }
  return 0;
}

2．裴波那契数列的递归求解算法。

#include<iostream>
using namespace std;
int Fib(int n){
  if(n<=2)return 1;
    return Fib(n-1)+Fib(n-2);
  }
int main(){
  int n;
  cin>>n;
  for(int i=1;i<=n;i++){
    cout<<Fib(i)<<endl;
  }
  return 0;
}

递推是数学上的概念，主要是指递推式或者说递推数列，递推函数，也就是说一个数列的下面一项有它的前面几项的值的一种运算（或者函数）构成，比如a[n]=a[n-1]+a[n-2];

递归是计算机中的概念，主要是指递归函数（计算机中函数同数学上函数意义也不相同，是指一段代码），就是指会调用自己的函数。显然，数学中的递推函数在计算机实现中可以通过递归来实现，但是不一定要通过递归来实现。