一、递归函数：从原理到实战

递归这个话题，说实话，我刚开始学C语言的时候也觉得挺绕的。但后来做了十几年嵌入式开发，发现递归其实是个很实用的工具——前提是你得真正理解它怎么工作。

今天我们就来聊聊递归函数的底层原理。我会结合栈帧的变化过程，把递归的"黑盒"彻底打开给你看。

1.1 什么是递归？

递归，说白了就是函数调用自己。但这里有个关键点：每次调用自己，都得带着不同的参数，否则就成死循环了。

来看一个最经典的例子——计算阶乘：

// 递归方式计算 n!
int factorial(int n) {
    if (n <= 1) {
        return 1;  // 递归终止条件
    }
    return n * factorial(n - 1);  // 递归调用
}

这个函数看起来简单，但背后发生的事情可不简单。每次调用 factorial(n - 1)，系统都会在栈上分配一块新的内存空间，用来存放这次调用的局部变量和返回地址。

核心要点：递归必须有两个部分——终止条件和递归调用。缺少任何一个，都会出问题。

1.2 栈帧的变化过程

我们以 factorial(4) 为例，看看栈帧是怎么一层层"叠"起来的。

调用过程是这样的：

  1. 第一次调用：factorial(4)，栈帧入栈，n=4
  2. 第二次调用：factorial(3)，新栈帧入栈，n=3
  3. 第三次调用：factorial(2)，新栈帧入栈，n=2
  4. 第四次调用：factorial(1)，新栈帧入栈，n=1

当 n=1 时，终止条件触发，开始"回溯"：

  1. factorial(1) 返回 1，栈帧出栈
  2. factorial(2) 计算 2*1=2，返回 2，栈帧出栈
  3. factorial(3) 计算 3*2=6，返回 6，栈帧出栈
  4. factorial(4) 计算 4*6=24，返回 24，栈帧出栈

嗯，这里有个细节你可能注意到了：每次递归调用都会创建一个新的栈帧。这意味着递归深度越大，栈空间消耗就越大。

我的经验：在嵌入式开发中，栈空间通常只有几KB到几十KB。我曾经在一个项目中用递归处理树形结构，结果递归深度到了100多层，直接栈溢出。从那以后，我对递归深度特别敏感。

1.3 递归深度限制与栈溢出

为什么会栈溢出？说白了就是栈空间用完了。每个栈帧的大小取决于函数的局部变量和参数。对于 factorial 函数，每个栈帧大概占用 16-32 字节（取决于平台）。

假设栈空间是 8KB，那么最多能容纳的递归深度大约是：

8 * 1024 / 32 = 256 层

这看起来不少，但实际项目中，函数往往有更多的局部变量，栈帧更大。再加上中断处理、其他函数调用，实际可用的递归深度会更小。

避坑指南：我曾经在调试一个通信协议栈时，发现程序偶尔会崩溃。查了两天才发现，是一个递归函数在特定数据模式下递归深度达到了 500 多层，直接撑爆了栈。解决方案是把递归改成了迭代，问题就解决了。

下面这张图展示了递归调用过程中栈帧的变化：

递归调用栈帧变化示意图 调用阶段（入栈） factorial(4) n=4, 返回地址 factorial(3) n=3, 返回地址 factorial(2) n=2, 返回地址 factorial(1) n=1, 返回地址 调用 调用 调用 终止 回溯阶段（出栈） 返回 1 返回 2 返回 6 返回 24 返回 返回 返回 返回 递归深度 = 4 层，栈空间消耗 = 4 × 栈帧大小 红色表示当前正在执行的栈帧，绿色表示已返回的栈帧

1.4 尾递归优化

尾递归是个好东西。它指的是递归调用发生在函数的最后一步，而且返回值直接返回，不再做任何计算。

拿阶乘来说，上面的写法不是尾递归，因为 n * factorial(n-1) 在递归返回后还要做乘法。改成尾递归需要引入一个累加器：

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

// 调用方式
int result = factorial_tail(4, 1);

尾递归的好处是什么？编译器可以优化它。优化后的效果是：不再创建新的栈帧，而是复用当前栈帧。这样递归深度就不再受栈空间限制了。

关键区别：普通递归是"先展开再计算"，尾递归是"边计算边递归"。尾递归本质上就是迭代，只是用递归的语法写出来。

但这里有个坑——不是所有编译器都支持尾递归优化。我记得 GCC 在 -O2 及以上优化级别会做尾递归优化，但有些嵌入式编译器就不一定了。所以写代码时不能完全依赖编译器优化。

1.5 递归 vs 迭代：怎么选？

我个人的习惯是：

  • 递归适合的场景：树形结构遍历、分治算法（如快速排序）、数学定义本身就是递归的（如斐波那契数列）
  • 迭代适合的场景：深度不确定或可能很深、性能要求高、栈空间紧张

举个例子，遍历二叉树用递归写起来很自然：

void traverse(TreeNode* node) {
    if (node == NULL) return;
    traverse(node->left);
    printf("%d ", node->data);
    traverse(node->right);
}

但如果树的深度可能达到几千层，那就得考虑用迭代+显式栈来实现了。

我的建议：在嵌入式开发中，除非你能确定递归深度很小（比如不超过 10 层），否则优先用迭代。我曾经在 STM32 上写一个菜单系统，递归深度最多 3 层，用递归就很舒服。

1.6 总结

递归函数的核心就三点：

  1. 栈帧变化：每次递归调用都会创建新栈帧，深度越大消耗越大
  2. 栈溢出风险：递归深度受栈空间限制，嵌入式开发中尤其要注意
  3. 尾递归优化：可以复用栈帧，但依赖编译器支持

写递归代码时，我建议你先问自己三个问题：递归深度最大是多少？栈空间够不够？能不能改成迭代？想清楚这些，递归就能成为你手中的利器，而不是定时炸弹。

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

← 上一章 📖 返回目录 下一章 →