递归

递归是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开始计算，而是可以直接使用之前计算过的数据，存储在数组中，这样可以大大减少程序运行的时间。