今日总结 – 关于递归算法的优化Ⅰ(以经典的斐波那契数列为例)

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

优化前

优化后

正文完