总结（递归）_递归 还原现场

概述

什么情况下用递归：大问题可以通过求解子问题求得，大问题与小问题有相同的特征
递归本质：通过自身调用自身缩小问题规模，边界条件结束，回溯还原现场

以原问题为起点尝试寻找把状态空间（一个实际问题各种可能的情况构成的集合）缩小到已知的问题边界的路线，再通过该路线返向回溯遍历的方式就是递归。

使用递归要求原问题与问题边界之间的每个变换步骤具有相似性，即遍历的每个状态都是相似的。即一个大问题可以转化为一个又一个子问题求解。

递归是深度优先搜索（DFS）的基础。

执行操作：

1.缩小问题状态空间的规模，程序尝试寻找在原问题与问题边界之间的变换路线，并向正在探索的路线上迈出一步
2.尝试求解规模缩小以后的问题，结果可能是成功，也可能是失败（自身调用自身）（由相同的程序求解）
3.如果成功，即找到了规模缩小后问题的答案，那么将答案扩展到当前问题，如果失败，那么重新回到当前问题（回溯时还原现场），程序可能会继续寻找当前问题的其他变换路线，直至最终确定当前问题无法求解。

递归实现指数型枚举：

#include <bits/stdc++.h>
using namespace std;
const int SIZE=10005;
int a[SIZE],c[SIZE*10];
vector<int> chosen;
int n;
void calc(int x)
{
    cout<<"这算一次"<<endl;
    if(x==n+1)
    {
        for(int i=0;i<chosen.size();i++)
        {
            cout<<chosen[i];
        }
        puts("");
        return ;
    }

    calc(x+1);//求解子问题
    chosen.push_back(x);//选x，x被压入chosen
    calc(x+1);//求解子问题
    chosen.pop_back();//准备回溯到上一问题之前，还原现场
}
int main()
{
    cin>>n;
    calc(1);
}

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

类似于深搜思想，一条路走到黑。我将代码中的上界设为3，即求1到3所有的组合，包括该数本身。那么该递归一开始就从头走到尾，找到了3,并输出出来，然后回溯还原现场即回到上一层状态空间，刚刚的影响全部消失，以此类推。

递归实现组合型枚举：
从1~n这n个整数中随机选出m个，输出所有可能的选择方案。

#include <bits/stdc++.h>
using namespace std;
const int SIZE=10005;
int a[SIZE],c[SIZE*10];
vector<int> chosen;
int n,m;
void calc(int x)
{
    if(chosen.size()>m||chosen.size()+(n-x+1)<m)//剪枝
        return;
    if(x==n+1)
    {
        for(int i=0;i<chosen.size();i++)
        {
            cout<<chosen[i];
        }
        puts("");
        return ;
    }
    calc(x+1);//求解子问题
    chosen.push_back(x);//选x，x被压入chosen
    calc(x+1);//求解子问题
    chosen.pop_back();//准备回溯到上一问题之前，还原现场
}
int main()
{
    cin>>n>>m;
    calc(1);
}

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

递归实现排列型枚举：

#include <bits/stdc++.h>
using namespace std;
const int SIZE=10005;
int a[SIZE],c[SIZE*10];
int n,m;
int order[20];
bool chosen[20];
void calc(int k)
{
    if(k==n+1)
    {
        for(int i=1;i<=n;i++)
        {
            cout<<order[i];
        }
        puts("");
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(chosen[i]) continue;
        order[k]=i;
        chosen[i]=1;
        calc(k+1);
        chosen[i]=0;
        order[k]=0;
    }
}
int main()
{
    cin>>n;
    calc(1);
}

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