递归与递推

题目练习：

• 递推：题库 - 蓝桥云课 (lanqiao.cn)
• 递归：题库 - 蓝桥云课 (lanqiao.cn)

递推

递推算法的基本概念

递推算法的特点

一个问题的求解需要大量重复计算，在已知的条件和所求问题之间总存在着某种相互联系的关系，在计算时，我们需要找到这种关系，进行计算（递推关系式）。

即递推法的关键，就是找到递推关系式，这种处理方式能够将复杂的计算过程，转化为若干步骤的简单重复运送，充分利用计算机运行程序时的时间局部性和空间局部性。

递推算法的思想：

1.首要问题是先找到各个相邻数据项之间的递推关系；

2.递推关系避开了求通项公式的麻烦，且有些题目的通项公式很难求，或者不能进行求解；

3.将复杂问题分解为若干步骤的简单运算；

4.一般来说递推算法就是一种特殊的迭代算法。

递推算法的一般步骤：

1.根据题目确定数据项，并找到符合要求的递推关系式；

2.根据递推关系式设计递推程序；

3.根据题目找到递推的终点；

4.单次查询可以不进行存储，多次查询都要进行存储；

5.按要求输出答案即可。

递推法的推广-42点问题

lanqiao1537：42点问题 - 蓝桥云课 (lanqiao.cn)

$\textcolor{red}{分析：}$

1. 

2. 创建 5 个 Vector ，分别用来存放 1-5 次的运算结果；

3. ans中运算的结果逐步的增多，避免了很多重复的运算。

解决代码：

#include<bits/stdc++.h>
using namespace std;
// 递推法的推广 
int a[7]; 
vector<int>ans[10];// 采用5个vector来存储经过5步运算之后得到的值，如：经过第一次运算之后的值存储在ans[1]中，ans[0]存储的是第一个操作数 

int main() {
	for(int i=0;i<6;++i){// 输入6个字符 
		char ch;
		cin>>ch;
		if(ch=='A')a[i] = 1;
		else if(ch=='J')a[i] = 11;
		else if(ch=='Q')a[i] = 12;
		else if(ch=='K')a[i] = 13;
		else a[i] = ch-'0';
	}
	ans[0].push_back(a[0]);// 初始化第一个操作数 
	for(int i=1;i<=5;++i){// 控制每步运算之后存储在 ans中的值 
		for(int j=0;j<ans[i-1].size();++j){// 将第i-1步运算得到的结果分别与当前字符进行运算，并将结果存储到第i步结果ans[i]中 
			ans[i].push_back(ans[i-1][j]+a[i]);
			ans[i].push_back(ans[i-1][j]-a[i]);
			ans[i].push_back(ans[i-1][j]*a[i]);
			ans[i].push_back(ans[i-1][j]/a[i]);
		}
	}
	bool flag = false;
	for(int j=0;j<ans[5].size();++j){
		if(ans[5][j]==42){
			flag = true;
			break;
		}
	}
	if(flag){
		cout<<"YES";
	}else{
		cout<<"NO";
	}
	return 0;
}

递归

递归算法的基本概念

递归算法：

递归算法是一种从自顶向下的算法，实际上是通过不停的直接调用或者间接的调用自身的函数，通过每次改变变量完成多个过程的重复计算，直到到达边界之后，结束调用。

与递推法相似的是，递归与递推都是将一个复杂过程分解为几个简单重复步骤进行计算。

递归算法的实现的核心是分治策略，即分而治之，将复杂过程分解为规模较小的同类问题，通过解决若干个小问题，进而解决整个复杂问题。

递归算法的思想：

1.将复杂计算过程转换为简单重复子过程；

2.找到递归公式，即能够将大问题转化为小问题的公式；

3.自上而下计算，在返回完成递归过程。

递归算法设计的一般步骤：

1.根据题目设计递归函数中的运算部分；

2.根据题目找到递归公式，题目可能会隐含给出，也可能需要自己进行推导；

3.找到递归出口，即递归的终止条件。

斐波那契数列

递推式：f(n) = f(n-1) + f(n-2)；

递推算法：

#include<bits/stdc++.h>
using namespace std;
int fib[25];
int main(){
    fib[1]=fib[2]=1;
    for(int i=3;i<=20;i++)  fib[i]= fib[i-1]+fib[i-2];
    cout <<fib[20];
}

递归算法：

#include<bits/stdc++.h>
using namespace std;
int cnt=0;                   //统计执行了多少次递归
int fib (int n){             //递归函数
    cnt ++;
    if (n==1 || n==2) return 1;  //到达终止条件，即最小问题        
    return fib (n-1) + fib (n-2); //递归调用自己2次，复杂度O(2n)
}
int main(){
    cout << fib(20);         //计算第20个斐波那契数
    cout <<" cnt="<<cnt;     //递归了cnt=13529次
}

• 递推和递归两种代码，结果一样，计算量差别巨大：

• 递推代码：一个for循环，计算20次。

• 递归代码：计算第20个斐波那契数，共计算cnt = 13529次。

• 为什么斐波那契的递归代码如此低效？——因为递归算法存在很多的重复计算

改进：记忆化（递归算法）

1. 递归的过程中做了重复工作，例如fib(3)计算了2次，其实只算1次就够了。

2. 为避免递归时重复计算，可以在子问题得到解决时，就保存结果，再次需要这个结果时，直接返回保存的结果就行了，不继续递归下去。

3. 这种存储已经解决的子问题结果的技术称为“记忆化（Memoization）”。

4. 记忆化是递归的常用优化技术。

5. 动态规划也常常用递归写代码，记忆化也是动态规划的关键技术。

改进算法：

#include<bits/stdc++.h>
using namespace std;
int cnt=0;         //统计执行了多少次递归
int data[25];      //存储斐波那契数
int fib (int n){
    cnt++;
    if(data[n]!=0) return data[n]; //记忆化搜索：已经算过，不用再算，直接返回结果    
if (n == 1 || n == 2) { data[n]=1; return data[n]; }    
    data[n] = fib (n-1) + fib (n-2);    //继续递归
    return data[n];
}
int main(){
    cout << fib(20);       //计算第20个斐波那契数
    cout <<" cnt="<<cnt;   //递归了cnt=37次。
}