递归是一种与递推恰好相反的逻辑；
递推是从前往后依次推理出来的结果，而递归是从后往前逆向推；
下面依次从三道简单题中了解递归；
AcWing 92. 递归实现指数型枚举

个人理解：第一题要求从n个数中选择任意个数，输出所有选择方案，且所有方案升序输出。
代码方法：u依次枚举n个数用并用state二进制位数表示数的选择或不选择

#include <iostream>

using namespace std;

int n;

void dfs(int u, int state) {
    if(u == n) //递归终止条件
    {
        for(int i = 0; i < n; i++) {//依次枚举n个数，并根据state状态输出，选择了就输出，没有就不输出
            if(state >> i & 1) cout << i+1 << ' ';
        }
        cout << endl;
        return ;//返回上一层
    }
    // else
    // {
        dfs(u + 1, state);//二进制位是1表示选择
        dfs(u + 1, state|(1<<u));//二进制位是0表示不选择
    // }
}
int main() {
    cin >> n;
    dfs(0, 0);//前面表示数的个数，后面表示数的状态
    return 0;
}

93. 递归实现组合型枚举

 第二题求从n个数中选择随意选择m个不同的数并升序输出。依旧是枚举所有数，用state表示选与不选
 对第一题代码稍作修改即可，**u表示枚举到了哪个数，用num表示选择了几个数，state表数的选择**；



#include <iostream>

using namespace std;

int n, m ;

void dfs(int u, int num, int state) {//选取参数
    if(num + n - u < m) return ; //边界条件***很重要
    if(num == m) 
    {
        for(int i = 0; i < n; i++) {
            if(state >> i & 1) cout << i+1 << ' ';
        }
        cout << endl;
        return ;
    }

        dfs(u + 1, num+1, state|(1<<u));
        dfs(u + 1, num, state);

}
int main() {
    cin >> n >> m;
    dfs(0, 0, 0);
    return 0;
}

94. 递归实现排列型枚举

 相较于前两道题是对数进行枚举并进行选与不选，第三道题是要求对数进行排列，
 所以我们可以将要排列的数，字符等等用坑（数组）去进行依次枚举填充并进行回溯，
 当一条路径填充完毕即数满足条件时就进行输出；


 解一：
#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int>num;

void dfs(int u, int state) {
    if(u == n) 
    {
        for(auto x : num) cout << x << " ";
        cout << endl;
        return;
    }
    for(int i = 0; i < n; i++)
    {
        if(!(state>>i&1))
        {
            num.push_back(i+1);
            dfs(u+1, state|(1<<i));
            num.pop_back();
        }
    }
}
int main() {
    cin >> n;
    dfs(0, 0);

    return 0;
}

解二：
#include <iostream>
#include <cstdio>
using namespace std;

int n;
int st[11];
bool vis[11];

void print(int n){
    for(int i = 1; i <= n; i++)
        printf("%d ",st[i]);
    printf("\n");
    return ;
}

void dfs(int u){
    if(u == n+1)
    {
        print(n);//打印
        return ;
    }
    for(int i = 1; i <= n; i++)
    {
        if(!vis[i])
        {
            st[u] = i;//表示已用过
            vis[i] = 1;
            dfs(u+1);
            st[u] = 0;//可省略
            vis[i] = 0;//复原
        }
    }
}

int main(){
    cin >> n;
    dfs(1);
    return 0;
}

思路来自yxc大佬，有错误之处大佬们多多指点！QWQ