21、递归函数：递归深度与栈溢出的陷阱

递归，说白了就是函数自己调用自己。

听起来很酷对吧？我刚开始学C语言那会儿，觉得递归简直是天才的发明——代码简洁、逻辑清晰，一个斐波那契数列几行就搞定了。直到有一次，我在一个嵌入式项目里用了递归，程序跑着跑着就挂了……嗯，从那以后，我对递归就多了一份敬畏。

递归的本质：栈的“叠罗汉”

每次函数调用，系统都会在栈上分配一块内存，叫“栈帧”。里面存着局部变量、返回地址这些东西。递归调用一次，就多叠一层栈帧。

你想想看，如果递归深度是1000，那栈上就有1000个栈帧叠在一起。栈空间是有限的——嵌入式系统里通常只有几KB到几十KB。叠得太高，栈就溢出了。

一个典型的“踩坑”例子

我见过不少新手这样写：

// 危险！没有终止条件的递归
void infinite_recursion(int n) {
    int local_var = 0;  // 每层都分配栈空间
    printf("Depth: %d\n", n);
    infinite_recursion(n + 1);  // 永远不返回
}

这个函数会一直递归下去，直到栈空间耗尽。在PC上可能还能撑一会儿，在单片机上？几毫秒就挂了。

再看一个“看起来没问题”的例子：

// 计算阶乘，递归实现
long factorial(int n) {
    if (n <= 1) return 1;  // 终止条件
    return n * factorial(n - 1);
}

这个代码逻辑是对的。但如果你调用 factorial(10000) 呢？

10000层递归，每层至少占几十字节栈空间。算下来几百KB。很多嵌入式系统的栈总共才1KB到8KB。结果就是——栈溢出，程序跑飞。

递归深度到底能到多少？

这取决于三个因素：

因素	说明	典型值
栈总大小	系统分配给栈的内存	1KB ~ 8KB（MCU） 1MB ~ 8MB（Linux）
每层栈帧大小	局部变量 + 返回地址 + 寄存器保存	16 ~ 128 字节
递归深度	函数调用自身的层数	取决于上面两个值

举个例子：一个STM32单片机，栈大小设为2KB。每层递归占用32字节。那么最大递归深度就是 2048 ÷ 32 = 64 层。超过64层，必挂。

递归 vs 循环：什么时候用哪个？

我个人经验是这样的：

• 能用循环解决的问题，优先用循环。循环不占额外栈空间，性能也更稳定。
• 递归适合处理“天然递归”的数据结构。比如树的遍历、图的深度优先搜索。这些用循环写反而更复杂。
• 递归深度可控时，可以用递归。比如二叉树深度最多logN，N=1000时深度也就10层左右，完全没问题。

我曾经在一个文件系统项目里，用递归遍历目录树。目录深度最多20层，递归写起来非常优雅。但如果目录深度可能达到几百层？那我绝对不敢用递归。

避坑指南：如何安全使用递归

我总结了几个实用方法：

1. 明确最大递归深度。写代码之前，先算清楚最坏情况下的递归层数。算不清楚就别用递归。
2. 加深度计数器。在递归函数里加一个静态变量或者参数，记录当前深度。超过阈值就报错返回。
3. 尽量减少每层的栈占用。把大数组、大结构体放到堆上或者全局区，别放在递归函数的局部变量里。
4. 考虑尾递归优化。某些编译器支持尾递归优化，可以把递归变成循环。但别依赖它——不是所有编译器都支持。

// 带深度保护的递归示例
#define MAX_RECURSION_DEPTH 100

int safe_recursion(int n, int depth) {
    if (depth > MAX_RECURSION_DEPTH) {
        // 记录错误日志，安全返回
        printf("ERROR: Recursion depth exceeded!\n");
        return -1;
    }
    if (n <= 1) return 1;
    return n * safe_recursion(n - 1, depth + 1);
}

知识体系：递归的核心逻辑

下面这张图，是我梳理的递归函数知识结构。你看一眼就能明白整个脉络：

最后说几句

递归是个好工具，但用不好就是一把双刃剑。我见过太多因为递归深度没控制好，导致线上设备死机的案例。尤其是在嵌入式领域，栈空间金贵得很，容不得半点浪费。

我的建议是：能用循环就别用递归，非用递归就一定要算深度。别等到程序跑飞了才后悔——那时候连调试都难。

---

公众号:蓝海资料掘金营，微信deep3321