GESP 3级 · 递归

📖概念讲解

递归，简单来说就是一个函数调用自己。听起来是不是有点疯狂？别急，用生活中的例子来理解：

俄罗斯套娃：你打开一个大套娃，里面是一个小一号的套娃，再打开又是一个更小的……直到最里面那个打不开了。递归就像这样，一个大问题拆成一个小一号的同样问题，层层缩小，直到遇到一个最简单的"打不开的套娃"——这就是递归出口（base case）。

递归有两个必要条件：

① 递归出口（Base Case）：什么时候停下来？没有出口就会无限调用，程序崩溃（栈溢出）。
② 递归调用（Recursive Case）：每次调用都要让问题变小，向出口靠近。

      经典例子 — 阶乘：

      5! = 5 × 4!，4! = 4 × 3!，……，1! = 1（出口！）

      所以 5! = 5 × 4 × 3 × 2 × 1 = 120

递归的核心思想：把大问题分解为结构相同的更小问题，直到问题小到可以直接回答。

💻代码示例

示例 1：用递归求阶乘

factorial.cpp

 1// 递归求阶乘 n!
 2int factorial(int n) {
 3    // 递归出口：0! = 1, 1! = 1
 4    if (n == 0 || n == 1) return 1;
 5
 6    // 递归调用：n! = n × (n-1)!
 7    return n * factorial(n - 1);
 8}
 9
10int main() {
11    cout << factorial(5); // 输出: 120
12    return 0;
13}

示例 2：斐波那契数列

fibonacci.cpp

 1// 递归求斐波那契数列
 2// F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2)
 3int fib(int n) {
 4    // 递归出口
 5    if (n <= 2) return 1;
 6
 7    // 递归调用：拆成两个更小的子问题
 8    return fib(n - 1) + fib(n - 2);
 9}
10
11int main() {
12    for (int i = 1; i <= 10; i++)
13        cout << fib(i) << " ";
14    // 输出: 1 1 2 3 5 8 13 21 34 55
15    return 0;
16}

      ⚠️ 注意：上面的斐波那契递归实现时间复杂度是 O(2ⁿ)，非常慢！实际比赛中通常会用记忆化（memoization）来优化，把算过的结果存起来避免重复计算。
    

🧩互动小测

Q1. 递归函数必须具备的两个要素是什么？

A. for 循环和 while 循环

B. 递归出口和递归调用

C. 全局变量和静态变量

D. 指针和引用

Q2. 下面代码的输出是什么？
int f(int n) { if(n==1) return 1; return n + f(n-1); }
调用 f(4) 结果是？

A. 4

B. 10

C. 24

D. 6

Q3. 如果递归函数缺少"递归出口"，会发生什么？

A. 编译错误，编译器会报错

B. 运行时栈溢出（Stack Overflow）

C. 函数自动返回 0

D. 程序会自动跳过递归

📝易错点提醒

❌ 忘记写递归出口

最常见的错误！没有出口会导致函数无限调用自己，最终 Stack Overflow 崩溃。写递归第一步就是先写 if 出口。

❌ 出口条件写错（差一错误）

比如阶乘应该在 n == 1 时返回，但写成了 n == 0——虽然数学上 0!=1，但如果递推是 n×f(n-1)，当 n=1 时会调用 f(0)，f(0) 又调用 f(-1)……一路调下去就爆了。务必确保每次调用都向出口靠近。

❌ 忽略递归的性能问题

朴素递归（如斐波那契）会有大量重复计算。考试中如果数据范围大（n > 30），需要记忆化或改成递推（用循环 + 数组）。

⚠️ 递归 vs 递推

递归是"自顶向下"调用自己；递推是"自底向上"用循环逐步计算。两者可以互相转换，但递推通常更快、更省内存。考试中灵活选择即可。

🏋️动手练一练

📝 编程练习

用递归实现汉诺塔问题：
有 A、B、C 三根柱子，A 上有 n 个从大到小叠放的圆盘。把所有圆盘移到 C 上，每次只能移动一个，且大盘不能压在小盘上。

要求：写出 hanoi(int n, char from, char mid, char to) 函数，并在 main 中调用 hanoi(3, 'A', 'B', 'C')。
提示：想想怎么把 n 个盘子的问题拆成 n-1 个盘子的问题。

参考答案：

#include <iostream>
using namespace std;

void hanoi(int n, char from, char mid, char to) {
    if (n == 1) {
        cout << from << " → " << to << endl;
        return;
    }
    hanoi(n - 1, from, to, mid);   // 先把 n-1 个盘子移到 B
    cout << from << " → " << to << endl;  // 移最大的到 C
    hanoi(n - 1, mid, from, to);   // 再把 n-1 个盘子从 B 移到 C
}

int main() {
    hanoi(3, 'A', 'B', 'C');
    return 0;
}
// 输出:
// A → C
// A → B
// C → B
// A → C
// B → A
// B → C
// A → C