概念
递归函数是指在函数体内直接或间接调用自身的函数。
递归是一种将大问题分解为相同结构的小问题来求解的编程技巧，在算法设计（如分治、回溯、动态规划）和数据结构（树、图）中应用广泛。
核心思想：
将问题规模逐步缩小，直到达到一个可以直接求解的“基准情形”，然后逐层返回结果。
基本原理
任何一个正确的递归函数必须包含两个关键要素：
| 要素 | 说明 |
|---|---|
| 基准情形（Base Case） | 问题规模足够小时，直接返回结果，不再递归调用。是递归的终止条件。 |
| 递归情形（Recursive Case） | 将原问题拆解为规模更小的同种子问题，通过调用自身来求解，并将子结果组合成原问题的解。 |
一般形式：
返回值类型 函数名(参数列表) {
if (基准条件) {
return 直接结果;
} else {
// 将问题分解，调用自身
return 函数名(缩小规模的参数);
}
}示例
阶乘（n!）
#include <iostream>
using namespace std;
// 递归计算 n! = n * (n-1) * ... * 1
long long factorial(int n) {
if (n < 0) return -1;
if (n == 0 || n == 1) return 1;
return n * factorial(n - 1);
}
int main() {
cout << factorial(5) << endl; // 输出 120
return 0;
}斐波那契数列
// 斐波那契数列：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)
long long fib(int n) {
if (n < 0) return -1;
if (n == 0) return 0;
if (n == 1) return 1;
return fib(n - 1) + fib(n - 2);
}该实现存在大量重复计算，效率极低（时间复杂度 O(2ⁿ)）。实际中可使用记忆化或迭代优化。
递归的优缺点
| 优点 | 缺点 |
|---|---|
| 代码简洁、逻辑清晰，特别适合分治、树/图遍历等问题 | 效率通常低于迭代（函数调用开销大） |
| 易于理解问题的分解结构 | 容易导致栈溢出（递归深度过大时） |
| 某些问题天然适合递归（如汉诺塔、快速排序） | 存在重复计算可能（如朴素斐波那契） |
| 使代码与数学归纳思想一致 | 占用更多内存（每层栈帧） |
常见问题与注意事项
缺少基准情形 → 无限递归
int bad_factorial(int n) {
return n * bad_factorial(n - 1); // 最终栈溢出
}递归深度过大 → 栈溢出
默认栈空间通常为 1~8 MB，每层栈帧几十字节到几百字节。深度超过 ~10⁵ 可能溢出。解决方法：
- 改用迭代
- 增大栈空间（编译器选项或
sys/resource.h） - 尾递归（如适用）
重复计算 → 效率爆炸
斐波那契朴素递归复杂度 O(2ⁿ)，应使用记忆化搜索（递归+缓存）或动态规划。
递归与迭代对比
| 方面 | 递归 | 迭代 |
|---|---|---|
| 代码长度 | 通常更短 | 可能较长 |
| 可读性（适合的场景） | 高（分治、树） | 中 |
| 时间复杂度 | 取决于算法，有重复计算时差 | 通常更优 |
| 空间复杂度 | O(深度) 栈空间 | O(1) 或 O(辅助空间) |
| 风险 | 栈溢出 | 无栈溢出风险 |
| 适用场景 | 问题天然具有递归结构（树、递归定义的数据结构） | 线性、简单循环即可表达的问题 |
递归是一种强大的思维工具，而不只是编码技巧。理解递归能帮助你更好地掌握分治、搜索、动态规划等高级算法思想。