10. 递归函数：递归原理，递归与迭代的对比，经典案例（阶乘、斐波那契）

好，咱们今天聊递归。说实话，递归这个概念，我当年学的时候也觉得有点绕。但后来在项目中用多了，发现它其实是个很优雅的工具——前提是你得理解它的脾气。

递归的原理：自己调用自己

递归，说白了就是一个函数在执行过程中，又调用了它自己。嗯，听起来有点“套娃”的意思。但关键在于，每次调用自己时，问题的规模都在缩小，直到遇到一个“不用再递归”的边界条件。

我习惯把递归拆成两个部分来看：

• 递推关系：当前问题的解，依赖于更小规模问题的解。
• 终止条件：当问题规模小到一定程度时，直接返回结果，不再递归。

你想想看，如果没有终止条件，递归就会无限进行下去，最终栈空间耗尽，程序崩溃。我在项目中就见过同事写的递归忘了加终止条件，结果一跑就段错误，排查了半天。

递归的调用过程：栈的视角

为什么递归能工作？这得感谢函数调用栈。每次函数调用，系统都会在栈上分配一块空间，用来存放局部变量、参数和返回地址。递归调用也不例外，每次自己调用自己，都会在栈上压入一个新的栈帧。

我画了一张图，帮你理解这个过程：

从图上你能看到，递归分两个阶段：递推（一路向下压栈）和回归（从底部开始向上返回）。当 fact(1) 触底返回 1 后，栈帧依次弹出，每层计算自己的结果，最终回到最顶层。

经典案例一：阶乘

阶乘是递归的“Hello World”。数学定义很直白：n! = n × (n-1)!，且 0! = 1。翻译成代码就是：

#include <stdio.h>

long long factorial(int n) {
    // 终止条件
    if (n <= 1) {
        return 1;
    }
    // 递推关系
    return n * factorial(n - 1);
}

int main() {
    int n = 5;
    printf("%d! = %lld\n", n, factorial(n));
    return 0;
}

运行结果：5! = 120。这个例子很简单，但我想提醒你注意一点：参数 n 每次减 1，最终一定会到达 1，所以递归是收敛的。如果你写的是 factorial(n+1)，那就永远到不了终止条件了——我曾经在代码审查时抓到过这种 bug。

经典案例二：斐波那契数列

斐波那契数列的定义：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)。递归实现非常直观：

#include <stdio.h>

long long fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

int main() {
    for (int i = 0; i <= 10; i++) {
        printf("F(%d) = %lld\n", i, fib(i));
    }
    return 0;
}

这段代码能跑，但我要给你提个醒：它的效率非常低。为什么？因为存在大量重复计算。你算一下 F(5)，它需要算 F(4) 和 F(3)；算 F(4) 又需要算 F(3) 和 F(2)……F(3) 被算了两次。随着 n 增大，重复计算呈指数级增长。

递归 vs 迭代：怎么选？

咱们来做个对比，我整理了一张表：

对比维度	递归	迭代
代码可读性	简洁，贴近数学定义	稍显繁琐，但逻辑直白
内存开销	每次调用压栈，深度大时可能栈溢出	通常只占用固定栈空间
执行效率	函数调用有额外开销，可能重复计算	通常更快，无调用开销
适用场景	树形结构、分治算法、数学定义明确的问题	线性遍历、累加累乘、简单循环

我个人习惯是：能用迭代解决的问题，优先用迭代。但遇到树遍历、汉诺塔、快速排序这类天然适合递归的问题，我不会硬写成迭代——那是在跟自己过不去。

递归的优化：尾递归

有一种特殊的递归叫尾递归——递归调用是函数的最后一个操作，并且返回值直接返回，不再参与额外计算。比如阶乘可以改写成尾递归形式：

long long factorial_tail(int n, long long acc) {
    if (n <= 1) {
        return acc;
    }
    return factorial_tail(n - 1, n * acc);
}

// 调用时：factorial_tail(5, 1)

尾递归的好处是：某些编译器可以优化成循环，从而避免栈溢出。但注意，C 标准并不强制要求编译器做尾递归优化，所以别完全依赖它。我在嵌入式开发中，一般还是老老实实写迭代。

递归的经典应用场景

除了阶乘和斐波那契，递归在以下场景中非常常见：

• 树的遍历：前序、中序、后序遍历，递归写法极其优雅
• 快速排序：分治思想，递归实现最自然
• 汉诺塔：不用递归，代码会变得非常复杂
• 文件系统遍历：目录嵌套深度未知，递归是天然选择

嗯，递归就聊到这儿。记住一句话：递归是思维工具，不是万能钥匙。该用的时候别犹豫，不该用的时候别逞强。

---