递归函数是在函数内部调用自己的函数，关键在于理解其调用与返回机制。1. 必须有明确的终止条件，否则会导致无限递归和栈溢出；2. 递归方向必须收敛，逐步接近终止条件；3. 应避免重复计算，可通过记忆化优化。例如阶乘函数通过逐层调用并利用栈帧保存状态，最终从最底层返回结果。递归适合处理分层结构问题，但需注意深度或改用迭代以避免栈溢出。
写递归函数，关键是要理解它怎么一层层调用、返回，以及每一步都干了什么。C++里的递归其实就是在函数里调自己，但每次调用都会生成一个新的栈帧，这些栈帧按“后进先出”的顺序被处理。
什么是递归函数？
递归函数就是函数内部调用自己的函数。要让递归能正常结束，必须有一个或多个终止条件（base case），否则就会无限调用下去，最终导致栈溢出。
举个简单例子：计算一个数的阶乘
立即学习“C++免费学习笔记（深入）”；
int factorial(int n) {
if (n == 0) return 1; // 终止条件
return n * factorial(n - 1); // 递归调用
}这个函数在调用 factorial(3) 的时候，会依次调用 factorial(2)、factorial(1)、factorial(0)，然后从 factorial(0) 开始往上返回结果。
递归的实现原理：栈帧是怎么工作的？
每次函数调用，系统都会为它分配一块栈帧（stack frame），里面保存着参数、局部变量、返回地址等信息。递归调用时，每一层都会有自己的栈帧，互不干扰。
比如上面的例子中：
- 调用
factorial(3)→ 创建第1层栈帧 - 调用
factorial(2)→ 创建第2层栈帧 - 调用
factorial(1)→ 创建第3层栈帧 - 调用
factorial(0)→ 创建第4层栈帧并返回1
之后，每层栈帧开始依次销毁，把结果带回上一层。
你可以想象成一摞盘子，每次调用就加一个盘子，到最底层拿到结果后再一个个拿回来。
写递归函数的关键点
1. 要有明确的终止条件
否则就会无限递归，直到程序崩溃。比如下面这个错误示例：
int badRecursion(int n) {
return n + badRecursion(n - 1); // 没有终止条件
}这会导致栈溢出（stack overflow）。
2. 递归方向要收敛
每次递归调用都应该向终止条件靠近。例如从 n 往 0 走，而不是反过来或者来回跳。
3. 避免重复计算
像斐波那契数列如果直接写成：
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}这种写法虽然正确，但效率非常低，因为会大量重复计算。可以用记忆化（memoization）来优化。
递归 vs 循环：什么时候该用哪个？
- 递归适合结构天然分层的问题，比如树和图的遍历、分治算法（如归并排序）、回溯问题。
- 循环通常更高效，没有栈帧开销，不会轻易溢出。
- 如果递归太深，建议改写成迭代形式，或者使用尾递归优化（不过C++编译器不一定支持）。
基本上就这些。写递归函数不是很难，但容易写错。关键是理清每一步怎么拆解、什么时候停下来，还有注意别让栈爆了。
