在此之前你需要具备一下知识：1. 一门编程语言基础，最好是C或者C++，其他语言如果你能看懂也可以看
如果你不具备以上知识，请你先补补课再来看
递归是啥我也不具体多说了，直接上代码。
初始的斐波那契代码：
#include <bits/stdc++.h>
using namespace std;
int fib(int n){
if(n == 1||n==2) return 1;
return fib(n-1)+fib(n-2);
}
int main(){
int n;
cin>>n;
int sum=fib(n);
cout<<sum;
return 0;
}优化后的斐波那契代码
#include <bits/stdc++.h>
using namespace std;
int fib(int n,int arr[]){
if(n == 1||n==2) return 1;
if(arr[n]==true) return arr[n];
arr[n]=fib(n-1,arr)+fib(n-2,arr);
return arr[n];
}
int main(){
int n;
cin>>n;
int arr[n];
memset(arr,0,sizeof(arr));
int sum=fib(n,arr);
cout<<sum;
return 0;
}递归式都是F(n-1)+F(n-2)，这里会调用两次递归，而两次递归中又有一些递归调用会有重复，所以，我们不妨把每次递归调用后的结果存在一个数组里，在下一次调用的时候直接判断其对应的数组是否有值，有的话直接输出，这样可以节省不必要的运算，从而降低算法的时间复杂度，但空间复杂度会有一定的增加。
