算法 | 递归与递推

递归与递推（上）

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 的二进制表示：00000000000000000000000000000001
• 1 << 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;
}