算法 | 递归与递推
递归与递推（上）
1.递归与递推的基本概念
在数学与计算机科学中，递归与递推是两种非常重要的概念，它们常用于定义序列、解决问题和设计算法。虽然两者看起来相似，但它们的本质和应用有所不同。
1.1 递归（Recursion）
递归是指一个过程（函数、公式等）直接或间接地调用自身。在递归的定义中，通常需要有基本情况（base case）来终止递归过程，否则递归会无限进行下去。
递归过程一般包含两个关键要素：
- 基本情况：递归终止的条件，避免了无限递归。
- 递归步骤：问题的一个子问题，通过调用自身来进行求解。
递归示意图
递归通常通过一个问题分解为相同类型的子问题来实现。下面的示意图可以帮助理解递归的过程：
问题 => 子问题1 => 子问题1的解
=> 子问题2 => 子问题2的解
=> 子问题3 => 子问题3的解
比如计算阶乘的递归方式： n!=n×(n−1)!，当 n=1 时返回 1。
阶乘递归例子：
5! = 5 × 4!
4! = 4 × 3!
3! = 3 × 2!
2! = 2 × 1!
1! = 1 （基本情况）
递归调用树示意图：
5!
/ \
5 * 4! 4!
/ \
4 * 3! 3!
/ \
3 * 2! 2!
/ \
2 * 1! 1
每个递归调用都进入更小的子问题，直到达到基本情况 1!=1，然后逐步返回计算结果。
1.2 递推（Recurrence）
递推是指通过前一个或前几个数值来逐步推算后续的数值。递推是一种通过已知信息进行推导和计算的过程，通常用公式来表示。
递推关系式包含：
- 初始条件：给定序列的前几个元素。
- 递推公式：使用前一个或前几个元素来计算下一个元素。
递推示意图
递推通常通过已知初值和递推公式，逐步推算出结果。下面的示意图描述了递推过程：
已知初值 -> 递推公式 -> 计算下一个数 -> 重复直到所有数值都被求出
例如，斐波那契数列是一个经典的递推关系： F(n)=F(n−1)+F(n−2)，初始条件：F(0)=0,F(1)=1。
斐波那契递推例子：
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
...
斐波那契数列递推示意图：
F(5)
/ \
F(4) + F(3)
/ \ / \
F(3)+F(2) F(2)+F(1)
/ \ / \ / \
F(2)+F(1) F(1)+F(0) F(1) F(0)
每一层递推都依赖于前面计算的数值，通过递推公式计算每个数值，直到初始条件 F(0)=0 和 F(1)=1 被找到。
1.3 递归与递推的区别
|特点|递归|递推| |-|-|-| |定义|问题通过调用自身来求解|使用已知的前几个元素来推算后续值| |过程|通过子问题的求解逐步深入，直到基本情况|通过递推公式，逐步计算后续数值| |终止条件|需要基本情况来避免无限递归|需要初始条件来开始递推| |实现方式|通常采用函数调用自己来实现|通常通过公式或循环来实现|
2.经典的算法题
2.1递归实现指数型枚举
题目链接：递归实现指数型枚举
从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。
输入格式
输入一个整数 n。
输出格式
每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好 1 个空格隔开。
对于没有选任何数的方案，输出空行。
本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。
数据范围
1≤n≤15
输入样例：
3
2.1.1解题思路
n个数每个数可选或不选
因为n≤15所以最多有2^15次方种状态
解题步骤
递归树的结构：
- 选择（选）：每个数都可以选择加入方案。
- 不选：每个数也可以选择不加入方案。
- 未考虑：对于每个数，我们有两个选择：选或者不选，递归的每个层级考虑这些选择。
递归回溯：
- 使用递归的方式从第一个数字开始，进行两种决策：
- 选：将当前数字加入当前的方案，并进入下一层递归。
- 不选：跳过当前数字，进入下一层递归。
- 递归会一直进行，直到达到所需的末端状态。
输出所有方案：
- 每一层递归的选择决定了最终生成的一个方案，所有可能的选择路径最终都会遍历并输出。
- 空集也应当作为一种结果输出，递归终止时可以返回一个空集合。
算法具体步骤：
- 递归函数：设定递归函数来生成所有选择方案。
- 回溯：每次递归返回时，如果当前数字被选，则继续进入下一层递归；如果不选，则跳过当前数字。
- 结果输出：所有递归结束时，存储并输出每个有效的结果。
时间复杂度：
- 对于每个数字来说，我们有两种选择（选或不选），所以总共有 2^n 种可能的选择方案。因此，时间复杂度为 O(2^n)。
2.1.2代码实现
头文件(最常用，后文的头文件也是这四个不再赘述
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
定义全局变量，注意是为了在dfs函数和主函数中都能用
const int N=16;//最多有15个数，遍历时从1开始所以N=16
int n;
int st[N];//记录每个数状态的数组 1选 -1不选
dfs函数
void dfs(int u)
{
if(u>n)//u从1开始，如果u>n递归结束
{
for(int i=1;i<=n;i++)//遍历记录状态的数组
{
if(st[i]==1)//被选的数 输出
{
printf("%d ",i);
}
}
puts("");//puts是输出字符串+回车，现在字符串为空相当于回车
return;
}
//递归
st[u]=1;
dfs(u+1);
st[u]=-1;
dfs(u+1);
}
主函数
int main()
{
cin>>n;
dfs(1);//从1开始考虑
return 0;
}
如果我们想要在dfs（）函数中记录全部状态
定义全局变量时应该添加一个二维数组记录状态
const int N=16;//最多有15个数，遍历时从1开始所以N=16
int n;
int st[N];//记录每个数状态的数组 1选 -1不选
int ways[1<<15][16],cnt=0;//cnt是计数器
在 C++ 中，1 << 15 是一种位操作表达式，它表示将整数 1 左移 15 位。
1 << 15 等价于 2^15，即 32768。左移运算相当于将数字乘以 2 的幂。
详细解释：
<<是 左移运算符，它会将一个数的二进制位向左移动指定的位数。- 在
1 << 15中，1是一个整数，它的二进制表示为0000...0001（假设为 32 位整数）。 - 通过左移 15 位，意味着把
1的二进制表示向左移动 15 个位置。移动后，1变成1000...0000（总共有 15 个零在1后面）。
举例：
假设我们使用 32 位的整数表示：
1的二进制表示：000000000000000000000000000000011 << 15的结果将是：10000000000000000000000000000000，即 32768。
修改dfs函数
void dfs(int u)
{
if(u>n)//u从1开始，如果u>n递归结束
{
/*for(int i=1;i<=n;i++)//遍历记录状态的数组
{
if(st[i]==1)//被选的数 输出
{
printf("%d ",i);
}
}
puts("");//puts是输出字符串+回车，现在字符串为空相当于回车*/
for(int i=1;i<=n;i++)
{
if(st[i]==1)//被选的数记录在数组中
{
ways[cnt][i]=[i];
}
}
cnt++;
return;
}
//递归
st[u]=1;
dfs(u+1);
st[u]=-1;
dfs(u+1);
}
在主函数中输出
int main()
{
cin>>n;
dfs(1);//从1开始考虑
for(int i=0;i<cnt;i++)
{
for(int j=1;j<=n;j++)
{
printf("%d ",ways[i][j]);
}
puts("");
}
return 0;
}
如果用vector来记录，代码如下
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=16;//最多有15个数，遍历时从1开始所以N=16
int n;
int st[N];//记录每个数状态的数组 1选 -1不选
vector<vector<int>> ways;//可变长的二维数组
void dfs(int u)
{
if(u>n)//u从1开始，如果u>n递归结束
{
vector<int> way;
for(int i=1;i<=n;i++)
{
if(st[i]==1)//被选的数记录在数组中
{
way.push_back(i);
}
}
ways.push_back(way);
return;
}
//递归
st[u]=1;
dfs(u+1);
st[u]=-1;
dfs(u+1);
}
int main()
{
cin>>n;
dfs(1);//从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;
}
2.2递归实现排列型枚举
题目链接：递归实现排列型枚举
把 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
2.2.1题目思路
解题思路
这个问题要求我们将 1∼n 这 n 个整数排成一行并输出所有可能的排列，按照字典序从小到大的顺序输出所有排列。
1. 排列的基本概念
排列是指从一组元素中选择并按顺序排列这些元素。对于 n 个整数 [1, 2, ..., n]，其所有可能的排列可以通过 n! (n的阶乘) 种方式排列出来。
在字典序中，我们要求按照每一位的数字进行逐一比较。可以理解为按升序排列每一组数字。
2. 如何生成所有排列
可以使用回溯算法（DFS）来生成所有排列。通过递归，我们可以逐步选择未使用的数字，并将这些数字填入排列中的每一个位置。递归深度达到 n 时，表示一个完整的排列生成，我们就可以打印它。
3. 回溯方法
- 使用一个数组（例如
used数组）来记录每个数字是否已经被选择。 - 在每层递归中，遍历所有可能的未选择的数字，选择一个数字并递归进入下一层。
- 当递归完成并回到上层时，需要恢复状态，允许该数字在其他分支中被选中。
4. 如何保证字典序
由于我们从小到大地遍历每一个数字，保证了排列的生成顺序是字典序的。换句话说，如果我们按顺序遍历数字并递归，那么生成的排列会按照数字的顺序依次排列，保证字典序。
2.2.2代码实现
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=10;
int n;
int st[N];//记录 输出方案 0表示未考虑
bool used[N];//记录数是否被选的状态 true 已选 false未选
void dfs(int u){
if(u>n)//边界
{
for(int i=1;i<=n;i++)
{
printf("%d ",st[i]);//依次输出方案中的数
}
puts("");
}
for(int i=1;i<=n;i++)
{
if(!used[i])
{
st[u]=i;//选中的数 记录下了
used[i]=true;
dfs(u+1);
used[i]=false;//回溯
}
}
}
int main()
{
cin>>n;
dfs(1);
return 0;
}
[N];//记录数是否被选的状态 true 已选 false未选
void dfs(int u){
if(u>n)//边界
{
for(int i=1;i<=n;i++)
{
printf("%d ",st[i]);//依次输出方案中的数
}
puts("");
}
for(int i=1;i<=n;i++)
{
if(!used[i])
{
st[u]=i;//选中的数 记录下了
used[i]=true;
dfs(u+1);
used[i]=false;//回溯
}
}
}
int main()
{
cin>>n;
dfs(1);
return 0;
}