关于递归算法的优化Ⅰ（以经典的斐波那契数列为例）

在此之前你需要具备一下知识：1. 一门编程语言基础，最好是C或者C ，其他语言如果你能看懂也可以看

如果你不具备以上知识，请你先补补课再来看

递归是啥我也不具体多说了，直接上代码。

初始的斐波那契代码：

代码语言：javascript复制

#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;
}

优化后的斐波那契代码

代码语言：javascript复制

#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)，这里会调用两次递归，而两次递归中又有一些递归调用会有重复，所以，我们不妨把每次递归调用后的结果存在一个数组里，在下一次调用的时候直接判断其对应的数组是否有值，有的话直接输出，这样可以节省不必要的运算，从而降低算法的时间复杂度，但空间复杂度会有一定的增加。

优化前

优化后

数据结构递归 栈 动态规划

0 人点赞