一、什么是尾递归？

尾递归，说白了就是递归函数的最后一步操作是调用自身。

嗯，这里要注意一个关键点：最后一步。不是最后一行，而是函数返回之前的最后一个动作。如果函数在递归调用之后还做了其他事情，那就不算尾递归。

我刚开始学递归时，也搞混过这个概念。后来在项目中调试栈溢出问题时，才真正理解了它的价值。

尾递归的定义

一个函数中，递归调用是函数体中最后执行的语句，并且递归调用的返回值直接被当前函数返回，没有额外的计算操作。

非尾递归 vs 尾递归

先看一个非尾递归的例子——普通阶乘：

// 非尾递归：计算 n!
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // 递归调用后还有乘法操作
}

为什么这不是尾递归？因为 factorial(n - 1) 返回后，还要乘以 n。编译器必须保留当前栈帧，等递归返回后再做乘法。

再看尾递归版本：

// 尾递归：计算 n!
int factorial_tail(int n, int acc) {
    if (n <= 1) return acc;
    return factorial_tail(n - 1, n * acc);  // 直接返回递归结果
}

这里递归调用的结果直接返回，没有额外操作。编译器看到这种模式，就可以做优化了。

二、编译器如何优化尾递归？

你想想看，普通递归每调用一次，就要在栈上分配一个新的栈帧。如果递归深度是10000，那就得压10000个栈帧。栈空间是有限的，很容易就爆了。

尾递归优化（Tail Call Optimization，TCO）的原理其实很简单：既然当前栈帧已经没用了，为什么不直接复用呢？

优化前后的对比

对比项	普通递归	尾递归（优化后）
栈帧数量	O(n)	O(1)
空间复杂度	O(n)	O(1)
栈溢出风险	高	低
执行效率	较低	接近循环

编译器具体怎么做？它会将尾递归改写为类似循环的形式。比如上面的 factorial_tail，优化后相当于：

// 编译器优化后的等效代码
int factorial_tail_optimized(int n, int acc) {
    start:
    if (n <= 1) return acc;
    acc = n * acc;
    n = n - 1;
    goto start;  // 跳回函数开头，复用当前栈帧
}

看到了吗？递归调用被替换成了 goto 跳转。栈帧始终只有一个，不会增长。

三、尾递归的核心逻辑图

下面这张图展示了普通递归和尾递归在栈使用上的本质区别：

左侧的普通递归，每调用一次就压一个新栈帧，深度越大栈空间占用越大。右侧的尾递归经过优化后，虽然逻辑上还是递归调用，但实际只用一个栈帧反复跳转。

四、用阶乘演示尾递归写法

阶乘是最经典的尾递归示例。我们一步步看怎么写：

普通阶乘（非尾递归）

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

这个版本的问题在于，每次递归调用都要等子调用返回后才能做乘法。栈帧不能释放。

尾递归阶乘

// acc 是累加器，保存中间结果
int factorial_tail(int n, int acc) {
    if (n <= 1) return acc;
    return factorial_tail(n - 1, n * acc);
}

// 封装函数，对外接口更友好
int factorial(int n) {
    return factorial_tail(n, 1);
}

这里的关键是引入了 acc（累加器）参数。每次递归时，把当前的计算结果传给下一次调用。最后一次递归返回时，acc 里已经存好了最终结果。

你看，每一步的结果都在 acc 里累积，不需要回溯计算。

五、用斐波那契演示尾递归写法

斐波那契数列的普通递归效率极低，因为存在大量重复计算。尾递归可以解决这个问题。

普通斐波那契（性能灾难）

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);  // 两次递归调用，指数级增长
}

这个版本的时间复杂度是 O(2ⁿ)。n=40 时就已经慢得无法忍受了。我在项目中见过有人用这个写法计算 fib(50)，程序直接卡死。

尾递归斐波那契

// a 和 b 保存前两个斐波那契数
int fib_tail(int n, int a, int b) {
    if (n == 0) return a;
    if (n == 1) return b;
    return fib_tail(n - 1, b, a + b);
}

// 封装函数
int fib(int n) {
    return fib_tail(n, 0, 1);
}

尾递归版本用两个累加器 a 和 b 来保存中间状态。每次递归时，把 b 赋给 a，a + b 赋给 b，相当于在数列上向前移动一步。

时间复杂度降为 O(n)，而且没有栈溢出风险。

六、尾递归的注意事项

如何判断编译器是否做了优化？

一个简单的方法：在递归函数里打印当前栈帧的地址。如果每次调用地址都相同，说明编译器做了TCO。

#include <stdio.h>

int fib_tail(int n, int a, int b) {
    printf("栈帧地址: %p, n=%d\n", &n, n);
    if (n == 0) return a;
    if (n == 1) return b;
    return fib_tail(n - 1, b, a + b);
}

int main() {
    int result = fib_tail(10, 0, 1);
    printf("结果: %d\n", result);
    return 0;
}

如果每次打印的地址都一样，恭喜你，编译器帮你优化了。如果地址在变化，说明没有开启优化或者编译器不支持。

七、总结

尾递归的本质，就是把递归改写成可以用迭代方式执行的形式。它保留了递归的清晰结构，同时避免了栈溢出的风险。

我个人习惯在以下场景优先考虑尾递归：

• 递归深度可能超过几百层
• 嵌入式系统或栈空间受限的环境
• 性能敏感的递归算法

记住一个口诀：尾递归，加累加器；最后一步，直接返回。 掌握了这个模式，你就能写出既优雅又高效的递归代码。

---

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