1.76、什么是尾递归？

关键点解析

• • 尾递归的定义：递归调用是函数的最后一步执行操作，且通常只有一次递归调用。
• • 优化原理：编译器检测到尾递归后，可以复用当前函数的栈帧，而不是为每次递归调用创建新的栈帧。这是因为尾递归调用后没有后续操作，调用返回时无需保存当前函数的上下文，因而可以用跳转（类似goto）替代调用，避免栈空间增长。
• • 性能优势：尾递归优化（Tail Call Optimization，TCO）使递归过程的栈空间使用保持常量级，避免了普通递归因栈帧累积导致的栈溢出风险，效率接近迭代实现。
• • C++支持情况：C++编译器通常支持尾递归优化，但标准并未强制要求，具体优化效果依赖编译器实现和代码写法。

示例（C++）

普通递归阶乘：

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1); // 递归调用后还有乘法操作，不是尾递归
}

改写成尾递归：

int factorialTail(int n, int acc = 1) {
    if (n <= 1) return acc;
    return factorialTail(n - 1, acc * n); // 递归调用是最后一步，符合尾递归
}

调用factorialTail(n)时，编译器可将递归转为循环，避免栈增长。
本文首发于【讳疾忌医-note】公众号，未经授权，不得转载。
（加入我的知识星球，免费获取账号，解锁所有文章。）