动态存储斐波那契数列（递归优化）
递归
递归是c++当中一种自身调用自身的算法。
普通递归解决斐波那契数列问题
#include<iostream>
using namespace std;
int f(int n){
int sum;
if(n<=2){
sum=1;
}else{
sum=f(n-1)+f(n-2);
}
return sum;
}
int main()
{
int n;
cin>>n;
cout<<f(n);
return 0;
}
当数据量比较大的时候，重复的内容会比较多，时间会很长。
优化后的斐波那契数列
#include<iostream>
using namespace std;
int arr[1001]={1,1};
int feibo(int n){
if(n<=2){
arr[n]=1;
}else{
if(arr[n-1]==0){
arr[n]=feibo(n-1)+feibo(n-2);
}else{
arr[n]=arr[n-1]+arr[n-2];
}
}
return arr[n];
}
int main(){
int end;
cin>>end;
cout<<feibo(end);
return 0;
} 
通过空间换时间，采用数组存储每次计算后的结果，这样当再次进行递归时，就不需要再重新从1开始计算，而是可以直接使用之前计算过的数据，存储在数组中，这样可以大大减少程序运行的时间。