递归的陷阱：栈溢出问题

递归这东西，用好了是神器，用不好就是炸弹。

我记得刚入行那会儿，写了个斐波那契数列的递归实现，自我感觉良好。结果一跑，程序直接崩了。当时我还纳闷——代码逻辑明明没问题啊？后来才知道，这就是典型的栈溢出。

说白了，递归调用会消耗栈空间。每次函数调用，系统都会在栈上分配一块内存，用来存局部变量、参数、返回地址。递归深度一大，栈空间就不够用了。

栈溢出是怎么发生的？

先看个简单的例子：

#include <stdio.h>

void recurse(int depth) {
    char buffer[1024];  // 每次调用分配1KB栈空间
    printf("深度: %d\n", depth);
    recurse(depth + 1);  // 无限递归
}

int main() {
    recurse(1);
    return 0;
}

这段代码跑起来，用不了多久就会崩。为什么？

每次调用 recurse，栈上都要分配 buffer 数组（1KB）加上其他开销。假设栈空间是8MB，那最多能递归8000次左右。超过这个数，栈就满了，再调用就会溢出。

如何估算最大递归深度？

这个问题，我在项目中遇到过好几次。估算递归深度，其实就三步：

1. 知道栈大小——Linux下默认是8MB，Windows下是1MB。可以用 ulimit -s 查看。
2. 算每次调用占多少——局部变量 + 参数 + 返回地址 + 寄存器保存。大概估一下就行。
3. 两者相除——栈大小 ÷ 每次调用开销 ≈ 最大递归深度。

举个例子：

栈大小	每次调用开销	最大递归深度
8 MB (Linux 默认)	约 200 字节	约 40000 次
1 MB (Windows 默认)	约 200 字节	约 5000 次
8 MB	约 1 KB (有局部数组)	约 8000 次

嗯，这里要注意：这只是理论值。实际运行时，系统本身也会占用一部分栈空间，所以安全深度要比理论值小一些。

递归深度过大怎么办？

我个人的习惯是：先问自己三个问题。

1. 能不能改成迭代？

很多递归都能用循环替代。比如遍历二叉树，用栈模拟递归：

// 递归版
void traverse_recursive(TreeNode* root) {
    if (!root) return;
    traverse_recursive(root->left);
    printf("%d ", root->val);
    traverse_recursive(root->right);
}

// 迭代版
void traverse_iterative(TreeNode* root) {
    TreeNode* stack[1000];
    int top = -1;
    TreeNode* curr = root;
    
    while (curr || top != -1) {
        while (curr) {
            stack[++top] = curr;
            curr = curr->left;
        }
        curr = stack[top--];
        printf("%d ", curr->val);
        curr = curr->right;
    }
}

迭代版虽然代码长了点，但栈空间是可控的。你想想看，递归版深度一深就崩，迭代版稳稳的。

2. 能不能用尾递归优化？

尾递归的意思是：递归调用是函数的最后一个操作。编译器可以把它优化成循环，不消耗额外栈空间。

// 普通递归
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // 不是尾递归
}

// 尾递归
int factorial_tail(int n, int acc) {
    if (n <= 1) return acc;
    return factorial_tail(n - 1, n * acc);  // 尾递归
}

不过要注意：C语言编译器不一定支持尾递归优化。GCC 用 -O2 或 -foptimize-sibling-calls 可以开启。但说实话，我一般不依赖这个，太不可控了。

3. 能不能增大栈空间？

这是最笨的办法，但有时候确实管用。

// Linux 下设置栈大小为 64MB
ulimit -s 65536

// 或者在代码里用 pthread 创建线程时指定栈大小
pthread_attr_t attr;
pthread_attr_init(&attr);
pthread_attr_setstacksize(&attr, 64 * 1024 * 1024);
pthread_t thread;
pthread_create(&thread, &attr, my_func, NULL);

我曾经在一个嵌入式项目里，默认栈只有64KB，递归深度稍微大点就崩。后来把栈调到256KB，问题就解决了。但这不是长久之计——栈大了，内存占用就大了，多线程场景下更明显。

知识体系总览

下面这张图，把栈溢出的核心逻辑串起来了：

避坑指南

我曾经在一个数据处理项目里，用递归遍历目录树。目录深度也就几十层，按理说没问题。但有个用户传了个特殊目录，里面全是符号链接，形成了循环。递归直接跑了几万层，栈溢出。从那以后，我写递归都会加个深度限制：

#define MAX_DEPTH 1000

void safe_recurse(int depth) {
    if (depth > MAX_DEPTH) {
        fprintf(stderr, "递归深度超限，终止\n");
        return;
    }
    // 正常逻辑
    safe_recurse(depth + 1);
}

嗯，这个习惯我一直保留着。你想想看，加一行判断，就能避免一次线上事故，多划算。

---