当前位置：首页 > article >正文

【从算法小白到 csp-j 一等第三节】递推与递归

article 2025/1/20 18:25:07

【从算法小白到 csp-j 一等第三节】递推与递归

前言
1 递推
- 1.1 递推的定义
- 1.2 递推的应用
2 递归
- 2.1 递归的定义
- 2.2 递归的优化
3 例题
- 3.1 [NOIP2003 普及组] 栈
- - 题目背景
  - 题目描述
  - 输入格式
  - 输出格式
  - 样例 #1
  - - 样例输入 #1
    - 样例输出 #1
  - 提示
  - 做法
- 3.2 台阶问题
- - 题目描述
  - 输入格式
  - 输出格式
  - 样例 #1
  - - 样例输入 #1
    - 样例输出 #1
  - 提示
  - 做法
4 习题
结语

前言

递归与地推在算法竞赛中的重要性及其重要，是之后动态规划与搜索的重要基础。

1 递推

1.1 递推的定义

递推指从给定条件出发，依据某种递推关系，依次推出所有中间结果及目标结果的方法。

1.2 递推的应用

以 $F ib o na cc i$ 数列为例，设 $F$ 为 $F ib o na cc i$ 数列，则 $F_0 = F_1 = 1$ ， $F_i = F_{i - 1} + F_{i - 2}$ ，其中 $F_i = F_{i - 1} + F_{i - 2}$ 就是递推关系。

可以开一个一维数组 $F$ 表示 $F ib o na cc i$ 数列，将初始值 $F_0$ 和 $F_1$ 设置为 $1$ ，后面从二开始一一递推即可。

const int N = 100010; // 数组大小，可以自己设置
int F[N] = {1, 1} // 设置初始值
int main()
{
	int n; // 需要计算的项数
	scanf("%d", &n);
	for (int i = 2; i <= n; i ++ ) // 从 2 到 n 递推
		F[i] = F[i - 1] + F[i - 2];
	printf("%d\n", F[N]);
	return 0;
}

当然，这个问题也可以用递归解决。

2 递归

2.1 递归的定义

递归指把一个大型复杂的问题层层转化为一个与原问题相似的、规模较小的问题来求解的方法。

递归有两个要求：

化成的子问题和原问题求解方法相同，只是数字大小不同。
递归次数有限，即递归到一定程度，递归函数可以结束，有结束的条件，即递归的边界。

$F ib o na cc i$ 数列同样也可以同递归解决，实现递归函数，函数调用自己实现转化为小问题解决。

int F(int x) // 递归函数
{
	if (x == 0 || x == 1) return 1; // 递归出口
	return F(x - 1) + F(x - 2); // 转化成子问题求解。
}
int main()
{
	int n;
	scanf("%d", &n);
	printf("%d\n", F(n));
}

递归的优势在于可以得到转化到每一个子问题的时间。如果在转化到每一个子问题时有输出，递归无疑是更好的选择。

递归还能在处理递推关系时更加方便。在 $F ib o na cc i$ 数列中，递推是直接从 $2$ 到 $n$ 枚举即可，但当问题的每个中间部分的求解顺序较为复杂时，这样做并不简单，而递归却没有这类问题。

递归还可以用于枚举，比如枚举长度固定，单调递减的序列。递归只需记录上一个数，即可确定当前数的范围。

2.2 递归的优化

但经过观察，我们发现，上述代码中，在 $n$ 很大时（ $n = 100000$ ），递归比递推慢很多，很长时间无法出解。原因是递归可能重复调用相同参数的递归函数，导致重复计算浪费时间。可以在每一个子问题计算完后，标记答案，下次再调用直接用之间计算的答案即可（前提是子问题结果只和函数参数有关）。

const int N = 100010;
int f[N]; // 储存之前的答案
int F(int x)
{
	if (f[x] >= 0) return f[x]; // 如果之前计算过不重复计算
	if (x == 0 || x == 1) f[x] = 1;
	else f[x] = F(x - 1) + F(x - 2); // 递归求解
	return f[x];
}
int main()
{
	int n;
	scanf("%d", &n);
	memset(f, -1, sizeof f); // 初始化成没有计算过
	printf("%d\n", &F(n));
}

这样递归就得到了优化。