蓝桥杯笔记——递归递推

递归

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 级台阶，那么你有两种选择：

1. 从第 n−1 级台阶爬一次 1 级。

2. 从第 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;}

分析：

1. factorial(n) 是一个递归函数，在 n == 1 时返回 1，这就是基准情况。

2. 否则，函数会调用 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));}}

分析：

1. factorial(n) 是一个递归方法，在 n == 1 时返回 1，这就是基准情况。

2. 否则，函数会调用 factorial(n - 1) 来计算下一个子问题，直到达到基准情况。

2.3 Python

Python 是一种更高层次的语言，它的递归写法非常简洁，并且函数的返回值和类型不需要提前声明。

 # 递归函数def factorial(n):# 基准情况if n == 1:return 1# 递推公式return n * factorial(n - 1)​n = 5print(f"Factorial of {n} is {factorial(n)}")

2.4 调用逻辑的图示

以阶乘为例子，其逻辑如下：

3. 常见问题

3.1 汉诺塔

对于汉诺塔问题，我们常用递归的思想来思考，我们尝试思考一个简单的问题，如果只有两个圆盘，应该如何操作？

我们稍作思考，可以得到如下方案：

那么我们得到的操作序列就是：

1. A→B

2. A→C

3. 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 osimport syscnt = 0​def hanoi(A, B, C, n):global cntif n == 1:cnt += 1if cnt == m: # 如果找到了第m步print(f"#{n}: {A}->{C}")else:hanoi(A, C, B, n - 1) # 第一步cnt += 1if 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 0elif n == 1:return 1a, b = 0, 1for i in range(2, n + 1):a, b = b, a + breturn bn = int(input())
print(f"Fibonacci({n}) = {fibonacci(n)}")

3. 例题

3.1 真题-全排列的价值

我们尝试用子问题分析的思想来进行思考。

1. 我们定义 f(n) 为 1∼n 中全排列的价值之和。

2. 思考 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 = 998244353def main():n = int(input())f = [0] * (n + 1)  # 用于存储 f[i] 的数组f[1] = 0p = 1  # 阶乘初始化为 1for i in range(1, n):p = p * i % MODf[i + 1] = (i * (i + 1) // 2 %MOD * p % MOD + f[i] * (i + 1) % MOD) % MODprint(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;  // 阶乘初始化为 1for (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. 总结

在分析递推题时：

1. 一般都是先定义递推的符号，即 f(n) 。

2. 然后根据现实意义进行分析，即从 n到 n+1 发生了什么变化。

3. 然后分析 n+1 产生的贡献，进行累加，得到递推关系。