0816更新
对于递归的补充，同样来自邓俊辉老师《数据结构C++》。
- 分支转向是算法的灵魂。
- 函数和过程及其之间的相互调用，是在经过抽象和封装之后，实现分支转向的一种重要机制
- 而递归是这种重要机制的特殊形式，因为允许函数和过程进行自我调用。具有高度的抽象性和简捷性
- 递归
- 递归的价值在于许多问题都可简介而准确的描述为递归形式
- 也是一种基本而典型的算法设计模式。可以对问题中反复出现的结构和形式作出高度概括，并从本质上加以描述和刻画，进而导出高效的算法
- 递归的复杂度计算
- 递归跟踪
- 递推方程
- 递归的代价
递归可以让我们在宏观上理解和把握问题的实质，深入挖掘和洞悉算法过程中的主要矛盾和一般性模式，并最终设计出简洁优美而精确紧凑的算法，然而众多优点的背后，隐含着某些代价
- 空间成本：
所消耗的空间量主要取决于递归深度，故较之同一算法的迭代版，消耗更多的空间，并进而影响实际的运行速度。如操作系统而言，为实现递归调用需要花费大量的时间以创建、维护和销毁各种递归实例，这也会令计算雪上加霜。- 解决方案：
一般的转换思路为：利用栈结构模拟操作系统的工作过程。
简单而常见的情况为：将尾递归转换为对应的迭代版本
-
递归的不同形式
- 线性递归：每次对自身调用至多一次
- 问题分解为两个独立的子问题：一个对应单独的某个元素，可直接求解。另外一个为剩余部分，结构与原问题相同
- 对应着 减而治之的算法策略decrease-and-conquer：递归每深入一层，待求解的问题的规模都将所见一个常数，直至最终退化为平凡的小（简单）问题。
- 若递归调用在递归实例中恰好最后一步操作的形式出现，则称为尾递归。注意是最后一步的操作，是实际的执行过程中，而并非语法的外在形式。尾递归都可以简捷的转换为等效的迭代算法
- 线性递归：每次对自身调用至多一次
-
二分递归：每一递归实例可能做多次递归，称为多路递归，通常将问题一分为二，故称为二分递归
- 对应着分而治之（divede-and-conquer）的策略，分解为若干个规模更小的子问题,(最好子问题都是独立的子问题，这样可以独立求解，而无需借助其他子问题的原始数据或中间结果。否则子问题之间相互传数据或者互相调用，导致了时间复杂度和空间复杂度的无谓增加，而对于子问题的重叠 【overlapping】/重复的递归实例，有对应的优化策略)
-
举例 数组求和
- 线性递归版 （注意不是尾递归，最后一步是加法，虽然语法形式是递归出现在最后一步）
//线性递归版本
int sum(int A[ ],int n){
if (n<1) // 平凡情况，递归基 可否理解为递归出口
return 0;
else // 一般情况
return sum(A,n -1 )+ A[n -1];
}
- 二分递归版本：以中间的元素将数组一分为二
int sum(int A[ ],int lo,int hi){
if(lo ==hi) return A[lo];
else{
int mi=(lo+hi)>>1;
return sum(A,lo,mi)+sum(A,mi+1,h1);
}
}
- 比较 ：
- 时间复杂度 o(n) 相同
- 空间复杂度 线性的为 o(n) 二分的为 o(logn) (递归深度-任一时刻活跃的递归实例的总数）
0815更新部分
今天看到了邓俊辉老师《数据结构C++》第一张的1.4节中 递归的优化策略的描述，又犯了嘀咕了，暂且先记录下来。
为了消除递归算法中重复的递归实例，一种自然而然的思路和技巧。可以概括为：
借助一定量的辅助空间，在各子问题求解之后，及时记录下其对应的解答
比如，可用从原问题出发自顶而下，每遇到一个子问题，都先查验它是否已经计算过，以期通过直接调阅记录获得解答，从而避免重复计算。
也可以从递归基出发，自底而上的递出各个子问题的解，直至最终原问题的解。
前者所谓的制表（tabulation)或记忆(memoization)策略，后者即所谓的动态规划策略
之前的理解制表和记忆是不等价的，还有待查阅更多资料。
- https://www.geeksforgeeks.org/tabulation-vs-memoization/
- 视频：Dynamic Programming | Set 1 (Solution using Tabulation) | GeeksforGeeks
不过看到邓公课件上写的 make it work,make it right,make it fast. 可以先用递归去思考问题，初步试验让其工作，为了提高效率，在用迭代去优化。
可能不应该太拘泥于这些概念的区别，应该知道如何把问题归类，找到更适合的方法去解决
【0814】
结论：
- 动态规划是一种思维方式，把大问题分解成若干个子问题，且子问题有重复，每个子问题只计算一次且保存其结果，这样下次遇到相同的子问题就直接用之前保存好的答案，最后合并子问题的解。(为什么叫动态这个名词，详见参考链接，故事还挺有意思）
- 递归是一种编程方式，函数调用其本身，不论是直接还是间接。
- 利用 递归 + 记忆化搜索 可以实现 自上而下的 动态规划
- 利用 迭代，先解决小问题，可以实现 自下而上的 动态规划
动态规划问题的两种类型
- 优化问题 如求最值
- 组合问题 做某件事的数量 或者 发生的概率
动态规划的解决方案
- 自上而下 :假设子问题已经解决
自上而下：你从最顶端开始不断地分解问题，直到你看到问题已经分解到最小并已得到解决，之后只用返回保存的答案即可。这叫做记忆存储（Memoization）
- 自下而上 :先解决子问题
自下而上：你可以直接开始解决较小的子问题，从而获得最好的解决方案。在此过程中，你需要保证在解决问题之前先解决子问题。这可以称为表格填充算法（Tabulation，table-filling algorithm**）。
动态规划与分冶治之
斐波那切数列
-
方案一：暴力递归
相同颜色的为重复子问题
int num=0; // count the number of fib call
vector <int> memo; // save the result of subquestion
int fib_recur(int n ){
num++;
if (n == 0) return 0;
if (n == 1) return 1;
return fib_recur(n-1)+fib_recur(n-2);
}
- 方案二：递归加记忆化搜索
int fib_recur_memo(int n ){
num++;
if (n == 0) return 0;
if (n == 1) return 1;
if(memo[n]== -1) // not see the situation befroe ,the memo it
memo[n] =fib_recur_memo(n-1)+fib_recur_memo(n-2);
return memo[n]; // if see it before , just look up and return
}
- 方案三：自下而上的迭代动态规划
int fib_recur_memo(int n ){
num++;
if (n == 0) return 0;
if (n == 1) return 1;
if(memo[n]== -1) // not see the situation befroe ,the memo it
memo[n] =fib_recur_memo(n-1)+fib_recur_memo(n-2);
return memo[n]; // if see it before , just look up and return
}
-
讨论
输入为30的结果比较
1.加记忆化的递归 调用自身的次数明显减少 ，为2n-1, 时间复杂度和 自下而上的迭代动态规划相同
2.自下而上的迭代 和 自上而下的 记忆的 本质区别在哪呢？
前者想一个无微不至（eager）的老管家，把所有一切都给你准备好了，不管你用的用不着。
-
后者是比较懒惰的（lazy）的管家，把你平常需要准备好了，如果需要的没有再去准备好了。
其他
动态规划和分冶策略
image.png
参考
- Dynamic Programming v.s. Memorization
- Dynamic Programming and Recursion | Difference, Advantages with Example
- slide: DP PART 1
- 动态规划的动态体现在哪里
- https://cs.stackexchange.com/questions/17871/what-is-dynamic-about-dynamic-programming
- dp VS divide-and conquer
完整代码
/* 斐波那契数列问题
- F(0)=1, F(1)=1,F(n)=F(n-1)+F(n-2)
递归方法 fib_recur
发现有重叠的子问题
1. 记忆化搜索 / 递归 （自上而下） fib_recur_memo
2. 迭代 （自下而上) fib_dp
*/
#include <iostream>
#include <vector>
#include <time.h>
using namespace std;
int num=0; // count the number of fib call
vector <int> memo; // save the result of subquestion
int fib_recur(int n ){
num++;
if (n == 0) return 0;
if (n == 1) return 1;
return fib_recur(n-1)+fib_recur(n-2);
}
int fib_recur_memo(int n ){
num++;
if (n == 0) return 0;
if (n == 1) return 1;
if(memo[n]== -1) // not see the situation befroe ,the memo it
memo[n] =fib_recur_memo(n-1)+fib_recur_memo(n-2);
return memo[n]; // if see it before , just look up and return
}
int fib_dp(int n){
num++;
vector<int> memo (n+1,-1);
memo[0]=0;
memo[1]=1;
for(int i =2;i<=n;i++) {
memo[i]=memo[i-1]+memo[i-2];
}
return memo[n];
}
int main(){
int n = 30;
memo=vector<int> (n+1,-1);
time_t startTime =clock();
int res=fib_dp(n); // change different func when u need to compare
time_t endtime=clock();
double usedtime=double(endtime-startTime)/CLOCKS_PER_SEC;
printf("fib(%d)=%d\n",n,res);
printf("used time : %f \n",usedtime);
printf("the number of fib called : %d",num);
return 0;
}
