学习目标与重点
掌握递归函数的定义、核心原理及适用场景，理解'递推 - 回归'过程。能够识别栈溢出、重复计算等常见问题并给出解决方案。同时了解尾递归的优化原理，学会根据实际场景在递归与迭代间做出选择。
核心重点：终止条件设计、尾递归与普通递归的区别、栈溢出规避。
递归函数基础认知
什么是递归函数
递归函数是指在函数体内部直接或间接调用自身的函数。其核心思想是'分而治之'——将大问题拆解为结构相同的小问题，直到小问题可直接求解（终止条件），再逐步回归得到原问题的答案。
生活中常见的递归案例包括俄罗斯套娃（层层嵌套直至最小）、阶乘计算（n! = n × (n-1)!）以及斐波那契数列。编写递归函数必须满足三个条件，否则会导致无限递归最终引发栈溢出：
- 终止条件：明确何时停止，返回确定值。
- 递归表达式：将原问题拆解为更小的子问题，结构需一致。
- 收敛性：每次调用都使问题规模缩小，趋近于终止条件。
执行过程解析
递归执行分为两个阶段：递推阶段和回归阶段。递推时函数不断调用自身拆解问题，触发终止条件后进入回归阶段，逐步返回结果。
以计算 n 的阶乘为例：
#include <iostream>
using namespace std;
// 递归计算 n 的阶乘
int factorial(int n) {
// 终止条件：0! = 1，1! = 1
if (n <= 1) {
return 1;
}
// 递归表达式：n! = n × (n-1)!
return n * factorial(n - 1);
}
int main() {
int n = 5;
cout << n << "! = " << factorial(n) << endl;
// 输出：5! = 120
return 0;
}
当 n=5 时，递推过程为 factorial(5) → 5 × factorial(4) → ... → 5×4×3×2×factorial(1)。回归时从 factorial(1) 返回 1，依次相乘得到 120。
常见应用场景
递归的优势在于代码简洁、逻辑清晰，特别适合具有'自相似性'的问题。
数学问题求解
除了阶乘，斐波那契数列、幂运算（a^b = a × a^(b-1)）以及最大公约数（欧几里得算法）都是经典应用。
例如求最大公约数：
// 递归求 a 和 b 的最大公约数
int gcd(int a, int b) {
// 终止条件：b=0 时，a 即为最大公约数
if (b == 0) {
return a;
}
// 递归表达式：gcd(a,b) = gcd(b, a%b)
return gcd(b, a % b);
}
int main() {
cout << gcd(12, 18) << endl; // 输出：6
cout << gcd(7, 5) << endl; // 输出：1
return 0;
}
数据结构遍历与操作
树的前序、中序、后序遍历，图的深度优先搜索（DFS），以及链表反转等操作，用递归实现往往比迭代更直观。
二叉树前序遍历示例：
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void preOrderTraversal(TreeNode* root) {
if (root == nullptr) return;
cout << root->val << " ";
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
组合与排列问题
子集生成、全排列、组合求和等问题通常使用回溯法（Backtracking），本质也是递归的一种变体。
常见问题与解决方案
栈溢出（Stack Overflow）
原因：递归深度过大导致栈帧耗尽，或缺少终止条件导致无限调用。
对策：
- 控制递归深度，确保不超过栈限制。
- 改用迭代实现，利用堆空间替代栈空间。
- 尝试尾递归优化（依赖编译器支持）。
将阶乘改为迭代实现可彻底避免栈溢出风险：
int factorial_iter(int n) {
if (n <= 1) return 1;
int result = 1;
for (int i = 2; i <= n; ++i) {
result *= i;
}
return result;
}
重复计算（效率低下）
部分递归（如斐波那契数列）会重复计算相同子问题，导致时间复杂度指数级增长。可通过记忆化搜索或动态规划解决。
记忆化优化示例：
#include <vector>
std::vector<int> memo;
int fib_memo(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
if (memo[n] != -1) return memo[n];
memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
return memo[n];
}
int main() {
int n = 30;
memo.resize(n + 1, -1);
cout << "F(" << n << ") = " << fib_memo(n) << endl;
return 0;
}
未优化的 F(30) 需百万次调用，记忆化后仅需 30 次，效率提升显著。
尾递归与 C++ 中的优化
什么是尾递归
尾递归指递归调用是函数的最后一条语句，且返回值直接作为当前函数的返回值，无额外计算。
对比普通递归与尾递归：
// 普通递归：递归调用后需执行乘法运算
int factorial_normal(int n) {
if (n <= 1) return 1;
return n * factorial_normal(n - 1); // 递归后有计算
}
// 尾递归：递归调用是最后一条语句
int factorial_tail(int n, int accumulator = 1) {
if (n <= 1) return accumulator;
return factorial_tail(n - 1, n * accumulator); // 无额外计算
}
优化原理
普通递归每次调用都在栈上创建新栈帧，而尾递归允许编译器复用当前栈帧，仅更新参数，本质上等价于迭代，从而避免栈溢出。但需注意，C++ 标准未强制要求编译器实现尾递归优化，GCC/Clang 在开启 -O2 后支持较好，VS 支持相对有限。
使用注意事项
- 显式开启优化：GCC/Clang 需通过
-O2或-O3编译选项启用。 - 确保末尾调用：递归调用后不能有表达式计算。
- 累积器传递：通过参数存储中间结果。
若编译器不支持优化，尾递归仍可能溢出，跨平台场景下迭代仍是稳妥之选。
递归与迭代的选择策略
| 维度 | 递归 | 迭代 |
|---|---|---|
| 可读性 | 高（逻辑简洁） | 低（需维护状态） |
| 时间效率 | 低（调用开销） | 高（无调用开销） |
| 空间效率 | 低（栈空间有限） | 高（堆空间大） |
| 适用场景 | 树/图遍历、分治 | 循环、大规模数据 |
建议：
- 优先递归：问题自相似性强，深度小，可读性优先。
- 改用迭代：深度大（如 n>1000）、性能敏感、防溢出。
- 折中方案：记忆化优化兼顾效率与可读性。
实战案例：汉诺塔
汉诺塔是经典递归问题。规则是将 n 个圆盘从 A 柱移至 C 柱，大盘不能压小盘。
思路：
- 终止条件：n=1 时直接移动。
- 递归表达式：
- 将 n-1 个从 A 移到 B（借助 C）。
- 将第 n 个从 A 移到 C。
- 将 n-1 个从 B 移到 C（借助 A）。
代码实现：
#include <iostream>
using namespace std;
void hanoi(int n, char from, char aux, char to) {
if (n == 1) {
cout << "移动圆盘 1 从 " << from << " 到 " << to << endl;
return;
}
hanoi(n - 1, from, to, aux);
cout << "移动圆盘 " << n << " 从 " << from << " 到 " << to << endl;
hanoi(n - 1, aux, from, to);
}
int main() {
int n = 3;
cout << "汉诺塔移动步骤（" << n << "个圆盘）：" << endl;
hanoi(n, 'A', 'B', 'C');
return 0;
}
递归完美贴合汉诺塔逻辑，代码简洁。若 n 极大，可转为迭代手动维护栈。
总结
递归的核心是'分而治之'，需满足终止条件、递归表达式、收敛性三大要素。它适用于树/图遍历、组合排列等自相似场景，但存在栈溢出和重复计算风险。尾递归可借助编译器优化为迭代，但需谨慎对待跨平台兼容性。实际开发中，应根据问题规模与性能需求权衡选择，必要时结合记忆化技术提升效率。