常用的递归算法：dfs（深度优先搜索），记忆化搜索，分治_dfs 深度搜索-从下向上(分治法)

递归值函数调用自身；

一、DFS的介绍

• 概念很简单，但是还是得了解一下，下面介绍的内容是重点

1. 图的DFS

（1）先看一下vector是怎么建图的？

vector<int> vecMap[100010];

// n条边（这个结点所连接的结点） 邻接表建图
for (int i = 0; i < n; ++i) {
	int x, y;
	vecMap[x].push_back(y);
	vecMap[y].push_back(x); //若是无向图就加上这一句
}

1
2
3
4
5
6
7
8
9

（2）图的DFS实现模板

// 假设这是个无向图
// 这里用DFS搜索所有的点（不是边）
// x代表搜到的当前的点
// 开一个搜索数组（标记）搜到为1，未搜到为0
int visited[100100];
void dfs(int x) {
	int i;
	visited[x] = 1; // 访问到了当前这个点，要标记为1，否则会陷入死循环
	for (i = 0; i < g[x].size(); ++i) {
		if (!visited[g[x][i]]) {
			// 若这个点的邻接点没有访问过（能走）就往这个邻接点走（递归这个邻接点）
			// 中间可以做一些其他的操作
			dfs(g[x][i]);
		}
	}	

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 比如连通块问题；
• 树形DP

（3）树的DFS实现模板

树（边数 = 顶点数 - 1 的图）的DFS
- 关于树，它是一个很特殊的图；
- 树更直观，它有层次有深度，也就是说
- 只要我们搜索的时候，搜到的不是该结点的父节点，那么就意味着我们没有搜过这个点
- 那我们就可以不用开标记数组了，在每一个递归的时候，把父节点一起传进去
- pr ：父节点，也可以说是这个结点的前一个结点
void dfs(int x, int pr) {
	// x为当前传入的结点
	for (int i = 0; i < g[x].size(); ++i) {
		if (g[x][i] != pr) dfs(g[x][i], x);
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13

二、使用DFS代替状压枚举：

1. 数位染色DFS写法

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll sum;
ll x;
int getSum (ll x) {
	int res = 0;
	while (x) {
		res += x % 10;
		x /= 10;
	}
	
	return res;
} 
int judge = 0; // 找到一个方案数，正好染色的数字之和等于总和的一半，就为true 

//x 代表当前这个数字（后面几个已经选过了，还有哪些位置还没有选，
//tmp 代表选了后面几位，我会选到什么 (已经选到的数字的和)
void dfs(ll x, ll tmp) { //12345 取 13
	
	if (x == 0 || tmp * 2 >= sum) {
		if (tmp * 2 == sum) {
			judge = 1;
		}
		return ;
	}
	
//	当前x%10的数不取，直接到下一个数
	dfs(x / 10, tmp); 
//	当前x%10的数取
	dfs(x / 10, tmp + x % 10);
	
}
int main () {
	cin >> x; // 输入的数字
	sum = getSum(x); // 求位置上的数字的和 
	dfs(x, 0);
	if (judge) cout << "Yes";
	else cout << "No";
	return 0;
} 
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

2. 记忆化搜索

记忆化搜索，指通过记录已经搜索到的值来降低重复操作次数，从而加快运行速度。用空间换时间；
拿个数组给它记录过程中的中间值

（1）举个例子：斐波那契数列

• 普通递归：O（2^n）

int f(int n) {
	if (n <= 1) return 1;
	return f(n - 1) + f(n - 2);
}
1
2
3
4

记忆化搜索：O（n）: 在搜索的过程中，把计算过的值用数组或STL容器存储下来，减少重复搜索的时间；这样遇到这个数就可以直接返回其值了

ll dp[100010] = {0};
ll f(ll n) {
	if (n <= 1) return dp[n] = 1; //赋值后将这个值返回
	if (dp[n]) return dp[n]; // 若记忆数组中有值，就把它返回
	return dp[n] = f(n - 1) + f(n - 2);
}
1
2
3
4
5
6

三、分治

将问题拆分成子问题进行求解。例如：归并排序