快速上手递归
本文认为你已经有了基本的编程能力，你只需要懂的什么是变量，什么是函数。懂的函数怎么调用，懂什么是函数的形参，使用过递归函数，但不太明白其中的意思即可。
递归搜索树
所有的递归都可转化为一个递归搜索树。
我们默认把它的边界放在函数的最上面。
我们常见的斐波拉契数列的递归搜索树如下：
a-2.jpg
斐波拉契数列的递归代码如下：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int dg(int u)
{
if (u == 1) return 1;//边界
if (u == 2) return 2;//边界
return dg(u-1)+dg(u-2);
}
int main()
{
scanf("%d", &n);
printf("斐波拉契数列的第%d位为%d\n", n, dg(n));
return 0;
}
运行结果如下：
a-3.png
用DFS来解决一个指数型枚举的问题。
题目如下：
从 1~n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。
输入格式
输入一个整数n。
输出格式
每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。
对于没有选任何数的方案，输出空行。
本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。
数据范围
1≤n≤15
输入样例：
3
输出样例：
3
2
2 3
1
1 3
1 2
1 2 3
思路
递归或DFS最重要的是顺序。
顺序不止一种，我们这里的顺序：从前往后依次考虑，选或者不选
也就是从1~n的位置依次考虑，选或者不选。（这里开始的位置用1，数组一般是0开头，但这里为了防止混淆就用1）
开一个长度为N的数组记录状态。
没选过是0，选是1，不选2.
DFS解决指数型枚举递归搜索树如下：
a-4.jpg
DFS解决指数型枚举代码如下：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 16;
int n;
int st[N]; //状态，记录每个位置当前的状态：0表示还没考虑，1表示选它，2表示不选它
void dfs(int u){
if (u > n){//已经到最后一位了
for(int i = 1; i <= n; i ++ )//这里从1开始循环，因为1是起点
if (st[i] == 1)
printf("%d ", i);
printf("\n");
return;
}
st[u] = 2;
dfs(u + 1); //第一个分支：不选
st[u] = 0; //恢复现场
st[u] = 1;
dfs(u + 1); //第二个分支： 选
st[u] = 0;
}
int main(){
cin >> n;
dfs(1);//传入一个开始的起点坐标 ，初学者从0开始比较乱，这里写个1
return 0;
}
DFS解决指数型枚举记录版代码如下：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 16;
int n;
int st[N];//状态，记录每个位置当前的状态:0表示还没考虑，1表示选它，2表示不选
//int ways[1<<15][15], cnt; //ways存方案 ，有2的15次方个，每个方案有15个数，cnt表示当前方案的数量是多少
vector< vector<int> > ways;
void dfs(int u){
if (u > n){
vector<int> way;
for(int i = 1; i <=n;i++)
if(st[i] == 1)
way.push_back(i);
//ways[cnt][i] == i;
ways.push_back(way);
//cnt++;
return;
}
st[u] = 2;
dfs(u + 1); //第一个分支：不选
st[u] = 0; //恢复现场 ,其实会自动还原 ，可以不写，但是为了更细 要知道要恢复现场，写了
st[u] = 1;
dfs(u + 1); //第二分支：选
st[u] = 0; //恢复现场 ,其实会自动还原 ，可以不写，但是为了更细 要知道要恢复现场，写了
}
int main(){
cin >> n;
dfs(1);
for(int i = 0; i < ways.size(); i ++){
for(int j = 0; j < ways[i].size(); j++) printf("%d ", ways[i][j]);
puts("");//等于输出一个空字符串加一个回车
}
return 0;
}
运行结果如下：
a-5.png
递归解决排列型枚举
题目如下：
把 1~n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。
输入格式
一个整数n。
输出格式
按照从小到大的顺序输出所有方案，每行1个。
首先，同一行相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。
数据范围
1≤n≤9
输入样例：
3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
思路
这个题目也就是平时所说的全排列。
思路我就直接发我纸质的笔记了。
a-6.png
a-7.png
a-8.png
递归解决排列型枚举代码如下：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 10;
int n;
int state[N];//存状态 0表示没存，1-n表示当前位置存的数
int used[N]; //记录数字状态 数字是否用过的,true表示用了，false表示没用过
//全排列顺序2：枚举位置放哪个数
void dfs(int u)
{
if ( u > n )
{//边界
for( int i = 1; i <= n; i ++ ) printf("%d ", state[i]);
puts("");
return;
}
//根据是否用过产生n个分支
for (int i = 1; i <= n; i ++ )
{
if( !used[i] )
{
//没用过,更新状态
state[u] = i;
used[i] = true;
dfs( u + 1 );
//恢复现场
state[u] = 0;
used[i] = false;
}
}
}
int main()
{
scanf("%d", &n);
dfs(1);
return 0;
}
递归解决排列型枚举运行结果如下：
a-9.png
递归解决组合型枚举
组合型枚举没有重复相同的序列。
思路和上面一样发我纸质的笔记了。
a-10.png
a-11.png
a-12.png
递归解决组合型枚举代码如下：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 30;
int n,m;
int way[N];
//顺序从小到大组合
void dfs(int u,int start)// u表示当前枚举到第几个位置， start表示我们从哪里开始枚举
{
//u-1 + n-start+1 =>>u+n-start
if(u + n - start< m) return; //剪枝 如果把后面所有数都选上，都不够m个，当前分支就一定无解
if ( u == m + 1 )//边界 u等于1时没有选，u == m+1 选了m个数
{//到这说明已经选了m个数
for (int i = 1; i <= m; i ++ ) printf("%d ",way[i]);
puts("");
return;
}
for(int i = start; i <=n; i ++ )
{
//更新状态
way[u] = i;
dfs(u + 1,i + 1);
//恢复现场
way[u] = 0;
}
}
int main()
{
scanf("%d%d", &n, &m);//从 1~n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案
dfs(1, 1);
return 0;
}
递归解决组合型枚举结果如下：
a-13.png
