C语言递归函数怎么优化？尾递归和记忆化实战详解

递归就是函数调用自身，每次调用在栈上压入新的栈帧（保存局部变量、返回地址），直到命中终止条件再逐层返回。三要素：终止条件、递归调用、向终止条件逼近——缺一个都会出问题。

递归最大的性能杀手是重复计算。经典的斐波那契 fib(n-1) + fib(n-2) 时间复杂度 O(2ⁿ)，因为同一值被反复算。两个主流解法：记忆化（用数组缓存已算过的值，降到 O(n)）和尾递归（把中间结果通过参数传递，编译器可复用当前栈帧而不压新帧）。

c
// 尾递归：累加器参数携带中间结果
int fib_tail(int n, int a, int b) {
    if (n == 0) return a;
    return fib_tail(n - 1, b, a + b);
}
// 调用：fib_tail(10, 0, 1)

关键细节：GCC 开 -O2 会把尾递归优化成跳转（相当于循环），不开优化就老老实实压栈——这意味着同样的尾递归代码在 Debug 和 Release 下行为可能完全不同。

追问

尾递归和普通递归在栈上的区别？

普通递归返回后还有事做（比如 n * factorial(n-1) 要等乘法），必须保留栈帧。尾递归的递归调用是函数最后一步，返回值直接向上传递，当前栈帧没用了，编译器可以复用它（tail call optimization）。效果上等价于 while 循环，栈深度始终是 O(1)。

C 编译器一定做尾递归优化吗？

不保证。C 标准没有强制要求 TCO，GCC/Clang 在 -O2 以上会做，MSVC 不做。而且只要递归调用不是严格最后一步（比如后面还有运算、或者有可观察的副作用），编译器就无法优化。所以生产代码别依赖 TCO，手写迭代更可靠。

递归转迭代有什么通用方法？

用显式栈模拟调用栈：把递归参数压栈，while 循环里弹栈处理，遇到需要"递归"的场景就压新参数。树的遍历是最典型的例子——前序遍历递归改迭代，就是把递归调用替换成压栈操作。

什么时候该用递归，什么时候该用迭代？

数据结构本身就是递归定义的（树、图、分治）用递归更自然。线性问题（求和、遍历数组）用迭代更直观也更高效。一个判断标准：如果递归深度可能超过几千层，就必须改迭代或用记忆化限制深度——Linux 默认栈大小 8MB，每帧几十字节的话，几万层就会栈溢出。