掌握 C++ 递归：核心原理、阶乘实战与优缺点权衡

C++ 递归完全指南

深入理解 C++ 递归函数：自我调用机制、基准条件终止、阶乘经典案例、栈溢出风险与尾递归优化。

函数调用自身称为递归函数，这种技术叫递归。

递归在 C++ 中如何工作

void Recurse() {
    // 递归前代码
    Recurse();  // 递归调用
    // 递归后代码
}

int main() {
    // 准备代码
    Recurse();
    // 收尾代码
}

递归持续直到满足基准条件。必须用条件分支（如 if...else）保证只有一条分支递归，否则无限递归导致栈溢出。

示例 1：递归计算阶乘

// 计算 n! = 1 × 2 × … × n
#include <iostream>
using namespace std;

int Factorial(int);

int main() {
    int n, result;
    cout << "Enter a non-negative number: ";
    cin >> n;
    result = Factorial(n);
    cout << "Factorial of " << n << " = " << result;
    return 0;
}

int Factorial(int n) {
    if (n > 1)
        return n * Factorial(n - 1);
    else
        return 1;
}

输出

Enter a non-negative number: 4
Factorial of 4 = 24

阶乘程序执行可视化

Factorial() 反复自调，每次 n 减 1。当 n ≤ 1 返回 1，递归展开，逐层相乘得最终结果。

递归的优缺点权衡

优势

• 代码简洁优雅：天然契合树、图、分治、回溯等递归结构问题
• 问题分解自然：将大问题分解为相同结构的小问题，符合数学归纳思维
• 不可变数据友好：函数式风格，无副作用，易于推理与并行

劣势

• 栈空间消耗大：每层调用占用栈帧，深度递归易栈溢出
• 函数调用开销：压栈/弹栈、寄存器保存恢复，比迭代慢
• 调试困难：深层调用栈难以追踪，变量值在多层间跳转
• 重复计算风险：如朴素斐波那契递归呈指数复杂度，需记忆化/动态规划优化

尾递归与优化

尾递归：递归调用是函数最后一个动作，无后续计算。编译器可优化为跳转（复用栈帧），避免栈溢出。

非尾递归（阶乘）

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, n * acc);  // 递归调用是最后动作
}

递归 vs 迭代：选型决策树

实战建议

1. 永远先写基准条件，再写递归步骤
2. 确保每次递归向基准条件收敛（参数变“小”或“简单”）
3. 考虑栈深度上限：Linux 默认 8MB 栈，约支持 10⁴~10⁵ 层简单调用
4. 可转为迭代时优先迭代，除非递归显著简化逻辑
5. 复杂递归用备忘录/动态规划消除重复子问题
6. 启用编译器优化（-O2）并验证汇编确认尾调用优化生效