递归

递归需要有基例、递归前进段和递归返回段（return语句），是一种程序设计技巧，可以使程序编写简单，但实际上要付出低效率的代价

计算时间复杂度常用数据的记忆（程序设计基本功，由于递归的低效，所以在程序设计的时候更要注意）

\(2^{20}\approx10^6\)
\(2^{16}=65536\)
\(2^{15}=32768\)
\(2^{63} \approx 10^{18}\)

用递归实现枚举操作

递归的数据结构表现之一为递归搜索树，因此在写递归函数的时候，我们通常把他们取名为dfs()（这也说明了在枚举这一操作中遍历这种树的办法常常是dfs)，在使用递归来进行枚举操作的时候，我们会从第一个步骤开始依次枚举不同的情况，生成由所有步骤组成的二叉树，再对树进行深度优先搜索，搜索到的每一个分支的最后的子节点就应该是问题的答案。

这里有两点值得注意：
1.在实际的程序运行中，我们并不是将二叉树生成完毕后，再对其进行深度优先遍历操作,而是在生成完父节点的子节点之后，对于已经完成当前分支情况的枚举结果的生成的分支进行回溯之后，对父节点进行**恢复现场**操作，将其状态重新变成未搜索状态，并进一步生成另外的一个子节点，重复这一过程。
2.由于有对时间复杂度的要求，在某些情况下，我们会对一些对结果不重要或者冗余的分支进行剪枝操作（实现一般也是寻找或构造出此种分支的特殊状态，用条件结构判断），这是降低时间复杂度的有效办法。

例题：
从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。
输入格式
输入一个整数 n。
输出格式
每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好 1 个空格隔开。
对于没有选任何数的方案，输出空行。
数据范围
1≤n≤15

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N=16;
int n;
int st[N];
//递归函数表示的是树的父节点的每一个子节点的生成逻辑，要抽象出逻辑来进行程序设计，不能简单地用顺序结构去理解，应该是（顺序结构+循环+迭代）（不太准确但好懂）
void dfs(int u)
{
	//递归返回段
        if (u>n)
	{
		for(int i=1;i<=n;i++)
			if(st[i]==1)
				printf("%d ",i);
		printf("\n");
		return;
	}
        //这两个分支是递归前进段：
        //分支1：
	st[u]=2;
	dfs(u+1);
	st[u]=0;
        //分支2：
	st[u]=1;
	dfs(u+1);
	st[u]=0;
}

int main()
{
	cin >> n;
	dfs(1);//这是基例
	return 0;
}