蓝桥杯笔记——递归递推
递归
0. 函数的概念
我们从基础讲起，先了解函数的概念，然后逐步引入递归，帮助同学们更好地理解递归的思想和实现方式。
函数是程序设计中的一个基本概念，简单来说，它是一段封装好的代码，可以在程序中多次调用，执行特定的任务。通过函数，程序员可以避免重复编写相同的代码，提高代码的可读性、可维护性，并减少出错的机会。
一个简单的比喻：
想象你在家做饭，每次做菜时，你需要切菜、煮菜、调味等步骤。如果每次做菜时你都要重新描述这些步骤，那就非常麻烦。函数就像是“做菜”的一个固定流程，你可以在任何时候用一句话调用“做菜”这个过程，而不用每次都重复描述这些步骤。
0.1 C/C++ 函数简要介绍
在 C/C++ 中，函数由函数名、参数列表、返回类型、以及函数体组成。通过函数，你可以将重复的代码块进行抽象，使得代码更加简洁。
示例：
一个简单的加法函数：
#include <bits/stdc++.h>
using namespace std;
// 函数定义
int add(int a, int b) {
return a + b;
}
int main() {
ios::sync_with_stdio(0),cin.tie(0);
int result = add(3, 5); // 调用函数
cout << "Result: " << result << endl; // 输出结果
return 0;
}解释：
-
int add(int a, int b)定义了一个接受两个整数参数并返回整数结果的函数。 -
add(3, 5)是函数的调用，计算 3+5。
0.2 Java 方法简要介绍
在 Java 中，函数被称为“方法”。方法同样也有返回类型、参数列表和方法体。Java 方法必须定义在类内部，不能像 C/C++ 那样独立存在。
示例：
public class Main {
// 方法定义
public static int add(int a, int b) {
return a + b;
}
public static void main(String[] args) {
int result = add(3, 5); // 调用方法
System.out.println("Result: " + result); // 输出结果
}
}解释：
-
public static int add(int a, int b)定义了一个公共的静态方法，返回一个整数。 -
add(3, 5)是方法的调用，计算 3 + 5。
0.3 Python 函数简要介绍
在 Python 中，函数的定义和调用方式更为简洁，语法也非常直观。Python 的函数定义使用 def 关键字。
示例：
# 函数定义
def add(a, b):
return a + b
result = add(3, 5) # 调用函数
print("Result:", result) # 输出结果解释
-
def add(a, b): 定义了一个函数add，接受两个参数。 -
add(3, 5)是函数的调用，计算 3 + 5。
1. 递归的概念与原理性理解
递归是程序设计中一种非常强大而且灵活的技术，它允许我们通过“自己调用自己”的方式来解决问题。说到递归，可能你会觉得有些抽象，但是不用担心，我会一步一步地带你走，帮助你把递归的核心思想掌握好。
我们先从一个简单的例子开始。假设你要爬楼梯，楼梯有 n* 级台阶，你每次可以选择爬 1 级或者 2 级。
如果你要到达第 n 级台阶，那么你有两种选择：
-
从第 n−1 级台阶爬一次 1 级。
-
从第 n−2 级台阶爬一次 2 级。
这就好像一个问题分解的过程，给你一个大问题（到达第 n 级台阶），你通过递归的方式分解成了两个小问题（分别到达第 n−1 和第 n*−2 级台阶）。每一步都可以继续递归，直到问题足够小，变得简单。
这就是递归的核心思想：通过将大问题分解成更小的相同问题来逐步求解。
递归的关键要素是：
-
递归的基准情况（Base Case）：当问题变得足够简单时，可以直接返回结果，不再进行递归调用。例如，爬楼梯时如果只剩1级台阶或者2级台阶时，你就能直接解决，不需要继续分解。
-
递归的递归公式：你通过递归的方式将一个大问题转化成多个小问题。每个小问题的解决方式是类似的，最终的解就是这些小问题的合成。
在爬楼梯的例子中，基准情况就是处于第 11 级台阶的情况。
再举个例子，假设你要求一个数的阶乘，阶乘的定义是：n!=n×(n−1)!
其中，当 n=1 时，阶乘的结果就是 1（这是基准情况）。
2. 递归的常见写法
我们以上述阶乘为例子分别展示三种代码的写法。
2.1 C/C++
在 C/C++ 中，递归的基本结构非常简单，通常包含一个递归函数和一个基准情况。
#include<bits/stdc++.h>
using namespace std;
// 递归函数
int factorial(int n) {
// 基准情况
if (n == 1) {
return 1;
}
// 递推公式
return n * factorial(n - 1);
}
int main() {
ios::sync_with_stdio(0),cin.tie(0);
int n = 5;
cout << "Factorial of " << n << " is " << factorial(n) << endl;
return 0;
}分析：
-
factorial(n)是一个递归函数，在n == 1时返回 1，这就是基准情况。 -
否则，函数会调用
factorial(n - 1)来计算下一个子问题，直到达到基准情况。
2.2 Java
在 Java 中，递归的实现方式与 C/C++ 类似，结构上几乎没有区别。我们同样通过递归函数来解决问题。
public class Factorial {
// 递归函数
public static int factorial(int n) {
// 基准情况
if (n == 1) {
return 1;
}
// 递推公式
return n * factorial(n - 1);
}
public static void main(String[] args) {
int n = 5;
System.out.println("Factorial of " + n + " is " + factorial(n));
}
}分析：
-
factorial(n)是一个递归方法，在n == 1时返回 1，这就是基准情况。 -
否则，函数会调用
factorial(n - 1)来计算下一个子问题，直到达到基准情况。
2.3 Python
Python 是一种更高层次的语言，它的递归写法非常简洁，并且函数的返回值和类型不需要提前声明。
# 递归函数
def factorial(n):
# 基准情况
if n == 1:
return 1
# 递推公式
return n * factorial(n - 1)
n = 5
print(f"Factorial of {n} is {factorial(n)}")2.4 调用逻辑的图示
以阶乘为例子，其逻辑如下：
3. 常见问题
3.1 汉诺塔
对于汉诺塔问题，我们常用递归的思想来思考，我们尝试思考一个简单的问题，如果只有两个圆盘，应该如何操作？
我们稍作思考，可以得到如下方案：
那么我们得到的操作序列就是：
-
A→B
-
A→C
-
B→C
在上述思路中，我们考虑的是两个圆盘的情况，如果是多个呢？
这就要求我们需要有分解子问题的思想，我们将两个圆盘中的小圆盘看成一个圆盘组，如下图：
这样是不是就可以看出是将一个圆盘组进行移动，恰好就对应了我们上述所说的子问题。
子问题分解：
我们定义函数/方法 hanoi(A,B,C,n) 将 n个圆盘从 A移动到 B。
那么在上述操作序列中的 A→B* 实际上就是调用 hanoi(A, C, B, n-1)，代表将前 n−1 个圆盘移动到 B杆。
然后将最后一个圆盘移动到 C 杆，最后需要将前 n−1 个圆盘从 B 移动到 C，那么就需要调用 hanoi(B, A, C, n-1)。
递归的基准情况：
当 n=1 时的情况下，那么就只需要执行一步即可。
以下给出代码：
-
C/C++
#include <bits/stdc++.h>
using namespace std;
int cnt = 0; // 计数器
int m; // 用于存储第 m 步
// 递归解决汉诺塔问题
void hanoi(string A, string B, string C, int n) {
if (n == 1) {
cnt++;
if (cnt == m) { // 如果找到了第 m 步
cout << "#" << n << ": " << A << "->" << C << endl;
}
} else {
hanoi(A, C, B, n - 1); // 第一步
cnt++;
if (cnt == m) { // 如果找到了第 m 步
cout << "#" << n << ": " << A << "->" << C << endl; // 第二步
}
hanoi(B, A, C, n - 1); // 第三步
}
}
int main() {
ios::sync_with_stdio(0),cin.tie(0);
int n; // 盘子的数量
cin >> n >> m; // 读取盘子数量和目标步骤
hanoi("A", "B", "C", n); // 递归调用汉诺塔函数
cout << cnt << endl; // 输出递归的总步数
return 0;
}-
Java
import java.util.Scanner;
public class Hanoi {
// 计数器
private static int cnt = 0;
// 用于存储第 m 步
private static int m;
// 递归解决汉诺塔问题
public static void hanoi(String A, String B, String C, int n) {
if (n == 1) {
cnt++;
if (cnt == m) { // 如果找到了第 m 步
System.out.println("#" + n + ": " + A + "->" + C);
}
} else {
hanoi(A, C, B, n - 1); // 第一步
cnt++;
if (cnt == m) { // 如果找到了第 m 步
System.out.println("#" + n + ": " + A + "->" + C); // 第二步
}
hanoi(B, A, C, n - 1); // 第三步
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 盘子的数量
m = scanner.nextInt(); // 目标步骤
hanoi("A", "B", "C", n); // 递归调用汉诺塔函数
System.out.println(cnt); // 输出递归的总步数
}
}-
Python
import os
import sys
cnt = 0
def hanoi(A, B, C, n):
global cnt
if n == 1:
cnt += 1
if cnt == m: # 如果找到了第m步
print(f"#{n}: {A}->{C}")
else:
hanoi(A, C, B, n - 1) # 第一步
cnt += 1
if cnt == m: # 如果找到了第m步
print(f"#{n}: {A}->{C}") # 第二步
hanoi(B, A, C, n - 1) # 第三步
n, m = map(int, input().split())
hanoi("A", "B", "C", n)
print(cnt)递推
1. 递推的概念与原理性理解
递推（Iteration）是通过反复地运算来推导一个问题的解的过程，通常是通过循环来实现的。我们可以将递推理解为从已知的初始条件出发，通过逐步推进的方式，逐步得出最终结果。可以把递推看成是一步一步“推”的过程，每次依赖于上一步的结果。
递推与递归的对比
递推和递归都属于“分解问题”的思想，即将一个大的问题分解成若干个小问题来求解，只不过它们的实现方式不同。
1. 递归的“函数调用”方式：
递归是通过函数自己调用自己来分解问题。每当问题可以分解成子问题时，递归就会被触发，直到找到最小的、无法继续分解的基础情况。
2. 递推的“循环推进”方式：
递推则是通过循环的方式，一步一步从初始状态推进，直到得到最终解。可以类比为走楼梯：从第一阶开始，逐步迈向下一阶，每一步都依赖于前一步的结果，直到爬到最后一阶。
递推的优点：
-
效率高：递推通常通过简单的循环来实现，不需要递归栈的支持，因此速度较快，内存开销较小。
-
简单：在大多数情况下，递推的写法非常简洁，适合解决问题时没有复杂的分解结构时。
递推的缺点：
-
难以扩展：递推在某些问题上不如递归灵活，尤其是在问题需要多层嵌套或复杂分解的情况下，递推的方式就显得比较局限。
2. 递推的常见写法
假设我们要求解斐波那契数列：
-
递归的做法：从公式 F(n)=F(n−1)+F(n−2) 出发，用递归方式计算每一个值。
-
递推的做法：通过从前两个数开始，逐步计算出后续的每一个数值。
斐波那契数列是：F(0)=0,F(1)=1,F(n)=F(n−1)+F(n−2) 。
通过递推的方式，我们可以用一个循环从 F(2) 开始，逐步计算出 F(n)。
2.1 C/C++
在C/C++中，递推通常使用for循环来实现。假设我们要求斐波那契数列的第n项：
#include <bits/stdc++.h>
using namespace std;
int fibonacci(int n) {
ios::sync_with_stdio(0),cin.tie(0);
if (n == 0) return 0;
if (n == 1) return 1;
int a = 0, b = 1;
for (int i = 2; i <= n; ++i) {
int temp = a + b;
a = b;
b = temp;
}
return b;
}
int main() {
int n;
cin >> n;
cout << "Fibonacci(" << n << ") = " << fibonacci(n) << endl;
return 0;
}2.2 Java
public class Fibonacci {
public static int fibonacci(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
int a = 0, b = 1;
for (int i = 2; i <= n; i++) {
int temp = a + b;
a = b;
b = temp;
}
return b;
}
public static void main(String[] args) {
int n = 10; // 这里可以替换成任意数字
System.out.println("Fibonacci(" + n + ") = " + fibonacci(n));
}
}2.3 Python
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
a, b = 0, 1
for i in range(2, n + 1):
a, b = b, a + b
return b
n = int(input())
print(f"Fibonacci({n}) = {fibonacci(n)}")3. 例题
3.1 真题-全排列的价值
我们尝试用子问题分析的思想来进行思考。
-
我们定义 f(n) 为 1∼n 中全排列的价值之和。
-
思考 f(n+1) 与 f(n) 的关系。
f(n+1) 相比于 f(n) 多了一个元素，那么实际上就是需要考虑多的这个元素 n*+1 应该放在排列中的哪个位置，同时会产生什么贡献。
我们简单考虑从排列 1∼2 到 1∼3。很明显 3 有三个位置可以放置。
如果放置在第二个位置，那么由于 3 比 1,2 都要大，所以放在第二个位置时，3 的前面有一个元素，所以贡献就是 1。
我们可以总结一下；如果放置在第 i 个与i+1 个元素之间，那么产生的贡献就是 i。
那么我们将所有位置的贡献都加起来就是
。当然这只是1∼n−1 固定排列的情况，当其不固定时，其贡献是
，同时由于 n+1 有 n+1 种放置方式，所以 f(n) 还需要扩充 n+1 倍。
于是得到递推公式：
以及初始条件：f(1)=0。由于只有一个元素，其全排列价值肯定为 0。
-
C/C++
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int f[N];
const int MOD = 998244353;
int main() {
ios::sync_with_stdio(0),cin.tie(0);
int n;
cin >> n;
f[1] = 0;
int p = 1; // 代表阶乘
for (int i = 1; i < n; ++i) {
p = 1ll * p * i % MOD;
f[i + 1] = 1ll * i * (i + 1) / 2 % MOD * p % MOD + 1ll * f[i] * (i + 1) % MOD;
f[i + 1] %= MOD;
}
cout << f[n] << '\n';
return 0;
}-
Python
MOD = 998244353
def main():
n = int(input())
f = [0] * (n + 1) # 用于存储 f[i] 的数组
f[1] = 0
p = 1 # 阶乘初始化为 1
for i in range(1, n):
p = p * i % MOD
f[i + 1] = (i * (i + 1) // 2 %MOD * p % MOD + f[i] * (i + 1) % MOD) % MOD
print(f[n])
if __name__ == "__main__":
main()-
Java
import java.util.Scanner;
public class Main {
static final int MOD = 998244353;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] f = new long[n + 1];
f[1] = 0;
long p = 1; // 阶乘初始化为 1
for (int i = 1; i < n; i++) {
p = p * i % MOD;
f[i + 1] = (i * (i + 1L) / 2L % MOD * p % MOD + f[i] * (i + 1L) % MOD) % MOD;
f[i + 1] %= MOD;
}
System.out.println(f[n]);
}
}4. 总结
在分析递推题时：
-
一般都是先定义递推的符号，即 f(n) 。
-
然后根据现实意义进行分析，即从 n到 n+1 发生了什么变化。
-
然后分析 n+1 产生的贡献，进行累加，得到递推关系。