16、递归调试：栈溢出与无限递归的排查
递归这东西，用好了是神器，用砸了就是噩梦。我见过太多同事在递归上栽跟头——程序跑着跑着突然崩了，或者干脆卡死不动。说白了，递归调试的核心就两个问题：栈溢出和无限递归。今天咱们就聊聊怎么逮住这两个捣蛋鬼。
16.1 递归的底层真相
先搞清楚一件事：递归调用本质上就是函数调用自己。每次调用，系统都会在栈上分配一块内存，用来存局部变量、参数和返回地址。这块内存叫栈帧。
我打个比方：就像你往一个桶里叠盘子，每调用一次就叠一个盘子。正常递归会一层层叠，再一层层取出来。但如果叠得太多，桶就满了——这就是栈溢出。如果只叠不取，那就是无限递归。
关键点：每个递归调用都会消耗栈空间。默认的栈大小通常是1MB到8MB，具体看平台。一旦超出，程序直接崩溃。
16.2 栈溢出的典型场景
我在项目中遇到过最典型的栈溢出，是处理一个深度嵌套的JSON结构。递归深度大概到了5000层，程序直接挂了。当时我还纳闷，明明逻辑没问题啊？后来一查，是递归深度太深了。
来看个简单的例子：
// 危险！递归深度过大
void deep_recursion(int n) {
char buffer[1024]; // 每个栈帧1KB
printf("Depth: %d\n", n);
deep_recursion(n + 1);
}
int main() {
deep_recursion(0);
return 0;
}这段代码跑不了几下就会崩。为什么？每个栈帧1KB，1MB的栈空间也就够1024层。实际上还要算上系统开销，可能500层就挂了。
避坑指南：我曾经在嵌入式设备上调试一个递归函数，栈空间只有256KB。递归深度超过200就崩。后来我把递归改成了迭代，问题就解决了。记住：嵌入式环境栈空间更小，递归要格外小心。
16.3 无限递归的排查方法
无限递归比栈溢出更隐蔽。程序不会立刻崩，而是卡死在那里，CPU飙到100%。你想想看，这种情况多难排查？
我总结了几种排查方法：
- 加递归深度计数器——最简单粗暴的方法
- 用调试器看调用栈——看函数调用链有没有重复
- 加日志输出——打印每次调用的参数
- 静态分析代码——检查递归终止条件
来看一个典型的无限递归：
// 无限递归！终止条件写错了
int factorial(int n) {
// 应该是 n <= 1，结果写成了 n >= 1
if (n >= 1) {
return 1;
}
return n * factorial(n - 1);
}这个例子很傻，但我在实际代码里见过类似的。当时同事写了个二叉树遍历，终止条件判断反了，结果递归永远停不下来。
16.4 调试递归的实用技巧
我个人习惯在调试递归时，先加一个深度限制。这样即使有bug，也不会把系统搞崩。
#define MAX_RECURSION_DEPTH 1000
int safe_recursion(int n, int depth) {
if (depth > MAX_RECURSION_DEPTH) {
printf("ERROR: Recursion depth exceeded!\n");
return -1; // 返回错误码
}
if (n <= 0) {
return 0;
}
return n + safe_recursion(n - 1, depth + 1);
}嗯，这里要注意：深度限制不能设太大，要根据栈空间来算。我一般会留50%的余量。
小技巧：用全局变量记录最大递归深度。程序跑完后看一眼，就知道实际深度是多少了。这样下次调优就有依据。
16.5 栈溢出故障的定位流程
当程序因为栈溢出崩溃时，怎么快速定位？我建议按这个流程来：
- 看崩溃日志——通常会有栈回溯信息
- 检查递归深度——是不是超出了预期
- 分析每个栈帧大小——有没有大数组或结构体
- 考虑改迭代——很多递归都能用循环实现
- 调整栈大小——作为最后手段
下面这张图展示了排查的核心逻辑：
16.6 实战案例：二叉树遍历的栈溢出
我记得有一次调试一个二叉树遍历程序。功能很简单，就是中序遍历打印节点值。但树特别大，有10万个节点。递归实现跑了几千层就崩了。
原代码是这样的：
void inorder_traverse(TreeNode* root) {
if (root == NULL) return;
inorder_traverse(root->left);
printf("%d ", root->value);
inorder_traverse(root->right);
}问题在哪？树不平衡！最坏情况下，10万个节点排成一条线，递归深度就是10万层。栈空间根本不够。
我当时的解决方案是改成迭代，用显式栈：
void inorder_iterative(TreeNode* root) {
TreeNode* stack[10000];
int top = -1;
TreeNode* curr = root;
while (curr != NULL || top != -1) {
while (curr != NULL) {
stack[++top] = curr;
curr = curr->left;
}
curr = stack[top--];
printf("%d ", curr->value);
curr = curr->right;
}
}改成迭代后，栈空间由我们自己控制，再也不用担心溢出了。说白了，递归虽然代码简洁，但有时候就是不适合深度大的场景。
经验之谈：我一般遵循这个原则——递归深度超过100层，就考虑改迭代。100层以内，递归代码更清晰，也更容易维护。
16.7 尾递归优化
有些编译器支持尾递归优化。说白了，就是如果递归调用是函数的最后一个操作，编译器可以复用当前栈帧，不分配新空间。
// 尾递归版本
int tail_factorial(int n, int acc) {
if (n <= 1) return acc;
return tail_factorial(n - 1, n * acc); // 尾调用
}但要注意：不是所有编译器都支持。GCC用-O2优化级别会做尾递归优化，但MSVC就不一定。我建议不要依赖这个特性，除非你很清楚目标平台的编译器行为。
避坑指南：我曾经以为编译器会做尾递归优化，结果在ARM平台上跑，栈还是爆了。后来一查，那个编译器版本不支持。从那以后，我再也不把尾递归优化当救命稻草了。
16.8 总结
递归调试说白了就三件事：控制深度、检查终止条件、监控栈使用。我个人习惯在写递归函数时，先加深度限制和日志输出。等逻辑验证没问题了，再考虑去掉这些调试代码。
记住：递归不是银弹。该用的时候用，该改迭代的时候别犹豫。你想想看，一个稳定的程序比一段看起来很酷的代码重要多了，对吧？