斐波那契数列的递推与递归求法

image-20220823103622471

斐波那契数列求法：递推（从前向后计算）、递归（从后向前计算），递归由于重复计算导致计算速度很慢——记忆化数组解决

1.递推求Fibonacci：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
using namespace std;

long long num[50] = {1, 1};

int main(){
    for(int i = 2; i < 50; ++i ){
        num[i] = num[i - 1] + num[i - 2];
    }
    for(int i = 1; i < 50; ++i){
        cout << i << " : " << num[i] << endl;
    }
    return 0;
}

image-20210412162623532

2.递归求Fibonacci：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
using namespace std;

long long func(int x){
    if(x == 0 || x == 1){
        return 1;
    }
    return func(x - 1) + func(x - 2);
}

int main(){
    for(int i = 1; i < 50; ++i){
        cout << i << " : " << func(i) << endl;
    }

    return 0;
}

image-20210412160848831

注意：可以看到这里利用递归法求斐波那契数列在进行到30项时，每一项的运算时间已经达到秒级

image-20220823104404729

3.递归求Fibonacci（记忆化数组优化）：

递归法中存在的大量重复计算导致递归递归太深、运算速度降低，可以使用记忆数组优化程序

  1. 定义一个记忆化数组用于存储运算过程中的中间值
  2. 当发现数字没有计算过，将数字计算一遍并将其存入数组中
  3. 当发现数字已经计算过，将存储的数值从数组中拿出直接使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
using namespace std;

//1.建立一个记忆化数组，存储计算过程中的中间值
long long num[50];

long long func(int x){
    if(x == 0 || x == 1){
        return 1;
    }
    //2.num[x] != 0,发现该数字之前已经计算过，直接返回数值
    if(num[x] != 0){
        return num[x];
    }
    //3.num[x] == 0,发现该数字之前没有计算过，进行计算并存入记忆化数组中
    return num[x] = func(x - 1) + func(x - 2);
}

int main(){
    for(int i = 1; i < 50; ++i){
        cout << i << " : " << func(i) << endl;
    }

    return 0;
}

image-20210412162721243

4.递推与递归间的转化

递推 ≈ 递归 + 记忆化数组，由于还有一个调用函数栈的过程只能是约等于