JC2 递推，递归与分治

递推，递归与分治

递推

1. 什么是递推

   递推，就是从小的解开始，一步一步推到最优解的过程。

2. 如何递推

   这就要看具体情况，想出递推式，然后一步一步递推即可。

3. 递推如何应用

   讲这个之前，我们不妨先讲一讲递推如何具体实现。

   第一步是先初始化。切记！

   有两种表示方法：

• 数组递推法，如 f[i] = f[i-1]+f[i-2];
• 记忆化搜索，若冗余状态比较多则需要记忆化，否则直接调用即可。注意递归的结束，否则MLE或TLE后果自负。

  那么，什么是冗余状态呢？

  

  这是一个关于f(5)的解答树，可以看见，红色的都是被重复计算的，很多节点被重复计算了多次，若数比较大，重复计算的可不止这几个，而是一颗巨大的子树。

  那么，没有记忆化的f究竟有多慢呢？

  我们可以做一个测试。

  代码如下：

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<ctime>
 5 using namespace std;
 6 int f(int i)
 7 {
 8     if(i == 0)return 0;
 9     if(i == 1)return 1;
10     return f(i-1)+f(i-2) % 233333333;
11 }
12 int main(int argc,char** argv)
13 {
14     int i = atoi(argv[1]);
15     cout<<f(i)<<endl;
16     cout<<"时间:"<<clock()/double(CLOCKS_PER_SEC);
17 }

1. 

   左图是笔者的vim截图，右图时代码在笔者机器上面的运行结果。

   可以看出，速度的增长是指数级的。

    

   我们在计算时用数组记录已经算出的结果，就是记忆化搜索的核心思想。

   但是，如果冗余状态比较少，或者没有，我们也可以不用记忆化。就像我们计算阶乘时，,很容易可以看出，每个状态只由前一个推出，所以，每个状态只被计算了一次。

递归

这个其实不用多说递归就是递推和回归，记忆化搜索就是递归的过程。

我们来看一个类似递归的故事：

1. 皇帝要计算f(5)（就是5!）.
2. 皇帝问大臣:f(4)=?
3. 大臣问师公:f(3)=?
4. 师公问先生:f(2)=?
5. 先生问小学生:f(1)=?
6. 小学生口算:f(1)=1
7. 先生口算:f(2)=2
8. 师公口算:f(3)=6
9. 大臣口算:f(4)=24
10. 皇帝口算:f(5)=120

皇帝满意了。
虽然这个比喻不是特别恰当，但是也能说明一些事情。

根据C++语言的特性，调用自己和调用其他函数并没有任何区别，都是压栈并修改当前代码行。