C++ 函数进阶：递归与尾递归优化

执行过程拆解（n=5）：

• 递推阶段：factorial(5) → 5 × factorial(4) → 5 × 4 × factorial(3) → 5×4×3×factorial(2) → 5×4×3×2×factorial(1)
• 回归阶段：factorial(1) 返回 1 → 2×1=2 → 3×2=6 → 4×6=24 → 5×24=120 → 最终返回 120

三、递归函数的常见应用场景

递归的核心优势是代码简洁、逻辑清晰，适合解决具有'自相似性'的问题，以下是 C++ 开发中常见的应用场景：

3.1 数学问题求解

• 阶乘计算（已示例）
• 斐波那契数列
• 幂运算（a^b = a × a^(b-1)）
• 最大公约数（GCD，欧几里得算法：gcd(a,b) = gcd(b,a%b)）

示例：欧几里得算法求最大公约数

// 递归求 a 和 b 的最大公约数
int gcd(int a, int b) {
    // 终止条件：b=0 时，a 即为最大公约数
    if (b == 0) {
        return a;
    }
    // 递归表达式：gcd(a,b) = gcd(b, a%b)
    return gcd(b, a % b);
}

int main() {
    cout << gcd(12, 18) << endl; // 输出：6
    cout << gcd(7, 5) << endl;   // 输出：1
    return 0;
}

3.2 数据结构遍历与操作

• 树的遍历（前序、中序、后序遍历）
• 图的深度优先搜索（DFS）
• 链表的反转、查找等操作

示例：二叉树前序遍历（根→左→右）

// 定义二叉树节点结构
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 递归实现前序遍历
void preOrderTraversal(TreeNode* root) {
    // 终止条件：节点为空
    if (root == nullptr) {
        return;
    }
    // 访问根节点
    cout << root->val << " ";
    // 递归遍历左子树
    preOrderTraversal(root->left);
    // 递归遍历右子树
    preOrderTraversal(root->right);
}

// 测试代码
int main() {
    // 构建二叉树：
    // 1
    //  \ 
    //   2
    //  /
    // 3
    TreeNode* root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);
    cout << "前序遍历结果：";
    preOrderTraversal(root); // 输出：1 2 3
    return 0;
}

3.3 组合与排列问题

• 子集生成（如求一个集合的所有子集）
• 全排列（如求 1~n 的所有排列方式）
• 组合求和（如从数组中找出和为目标值的所有组合）

示例：生成 1~n 的所有子集

#include <vector>

void backtrack(int n, int start, vector<int>& path, vector<vector<int>>& result) {
    // 终止条件：无明确终止值，每次递归都将当前路径加入结果集
    result.push_back(path);
    // 递归表达式：遍历剩余元素，加入路径后递归
    for (int i = start; i <= n; ++i) {
        path.push_back(i); // 选择当前元素
        backtrack(n, i + 1, path, result); // 递归处理下一个元素
        path.pop_back(); // 回溯：撤销选择
    }
}

// 生成 1~n 的所有子集
vector<vector<int>> subsets(int n) {
    vector<vector<int>> result;
    vector<int> path;
    backtrack(n, 1, path, result);
    return result;
}

int main() {
    int n = 3;
    vector<vector<int>> res = subsets(n);
    cout << "1~" << n << "的所有子集：" << endl;
    for (auto& subset : res) {
        cout << "[";
        for (int i = 0; i < subset.size(); ++i) {
            if (i > 0) cout << ",";
            cout << subset[i];
        }
        cout << "] ";
    }
    // 输出：[][1][1,2][1,2,3][1,3][2][2,3][3]
    return 0;
}

四、递归函数的常见问题与解决方案

递归虽简洁，但存在潜在问题，需针对性优化：

4.1 问题 1：栈溢出（Stack Overflow）

原因：

• 递归深度过大（如计算 n=10000 的阶乘），每次递归调用都会在栈上分配函数栈帧（存储参数、局部变量、返回地址），栈空间有限（默认栈大小通常为几 MB），超出后触发栈溢出。
• 缺少终止条件或终止条件错误，导致无限递归。

解决方案：

1. 控制递归深度：确保问题规模不会导致递归深度超出栈限制（如 n 不超过 1000）。
2. 改用迭代实现：将递归转换为循环，手动维护栈或状态（栈空间由堆空间替代，容量更大）。
3. 使用尾递归优化（部分编译器支持）：将递归调用放在函数末尾，编译器可优化为迭代，避免栈溢出。

示例：将阶乘的递归实现改为迭代实现

int factorial_iter(int n) {
    if (n <= 1) return 1;
    int result = 1;
    // 循环替代递归，手动累积结果
    for (int i = 2; i <= n; ++i) {
        result *= i;
    }
    return result;
}

int main() {
    cout << factorial_iter(1000) << endl; // 无栈溢出风险
    return 0;
}

4.2 问题 2：重复计算（效率低下）

原因：

部分递归问题（如斐波那契数列）会重复计算相同的子问题，导致时间复杂度呈指数级增长（如计算 F(10) 需重复计算 F(8)、F(7) 多次）。

解决方案：

1. 记忆化搜索：使用数组或哈希表存储已计算的子问题结果，避免重复计算。
2. 动态规划：通过迭代方式，从底向上计算子问题结果，逐步推导原问题答案。

示例：斐波那契数列的记忆化优化

#include <vector>

// 记忆化数组：存储已计算的 F(n) 结果
vector<int> memo;

int fib_memo(int n) {
    // 终止条件
    if (n == 0) return 0;
    if (n == 1) return 1;
    // 若已计算，直接返回缓存结果
    if (memo[n] != -1) {
        return memo[n];
    }
    // 计算并缓存结果
    memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
    return memo[n];
}

int main() {
    int n = 30;
    memo.resize(n + 1, -1); // 初始化记忆化数组
    cout << "F(" << n << ") = " << fib_memo(n) << endl; // 输出：832040
    return 0;
}

对比：未优化的斐波那契递归计算 F(30) 需执行约 100 万次函数调用，记忆化优化后仅需 30 次，效率提升显著。

五、尾递归与 C++ 中的优化

5.1 什么是尾递归

尾递归是指递归调用是函数的最后一条执行语句，且递归调用的返回值直接作为当前函数的返回值（无额外计算）。

普通递归 vs 尾递归：

// 普通递归：递归调用后需执行乘法运算（n × 结果）
int factorial_normal(int n) {
    if (n <= 1) return 1;
    return n * factorial_normal(n - 1); // 递归后有计算
}

// 尾递归：递归调用是最后一条语句，无额外计算
int factorial_tail(int n, int accumulator = 1) {
    if (n <= 1) return accumulator; // 累积器存储中间结果
    // 递归调用是最后一条语句，返回值直接返回
    return factorial_tail(n - 1, n * accumulator);
}

5.2 尾递归的优化原理

普通递归的每次调用都会在栈上创建新的栈帧，而尾递归的递归调用在函数末尾，编译器可优化为'复用当前栈帧'——无需创建新栈帧，仅更新函数参数（如累积器、n 的值），本质上等价于迭代，避免栈溢出。

关键：尾递归的优化依赖编译器支持，C++ 标准未强制要求编译器实现尾递归优化，但 GCC、Clang 等主流编译器在开启优化选项（如 -O2）后支持该特性，VS 编译器的支持相对有限。

5.3 C++ 中尾递归的使用注意事项

1. 显式开启优化：在 GCC/Clang 中，需通过编译选项 -O2 或 -O3 启用尾递归优化（默认 -O0 不优化）。
   • 编译命令：g++ -O2 main.cpp -o main
2. 确保递归调用在末尾：递归调用后不能有任何表达式计算（如 return tail(n-1) + 1 不是尾递归）。
3. 使用累积器传递中间结果：尾递归需通过参数（如 accumulator）存储中间结果，避免递归返回后进行计算。

示例：尾递归计算阶乘（GCC -O2 优化后无栈溢出）

#include <iostream>
using namespace std;

// 尾递归计算阶乘，accumulator 为累积器（默认值 1）
long long factorial_tail(int n, long long accumulator = 1) {
    if (n <= 1) {
        return accumulator;
    }
    // 递归调用在末尾，无额外计算
    return factorial_tail(n - 1, n * accumulator);
}

int main() {
    // 计算 10000 的阶乘（普通递归会栈溢出，尾递归优化后正常运行）
    cout << "10000! 的结果（前 20 位）：";
    long long result = factorial_tail(10000);
    // 输出结果（实际结果极长，此处仅展示前 20 位）
    cout << result << endl;
    return 0;
}

警告：若编译器不支持尾递归优化，尾递归仍会产生栈溢出，因此在跨编译器场景下，迭代实现仍是更稳妥的选择。

六、递归与迭代的选择策略

选择建议：

1. 优先使用递归：问题具有明显自相似性，递归深度小，且代码可读性优先级高于性能（如二叉树遍历、子集生成）。
2. 改用迭代：递归深度大（如 n>1000）、性能要求高、需避免栈溢出（如大规模数据计算）。
3. 折中方案：对递归进行记忆化优化，兼顾可读性和效率（如斐波那契数列、动态规划问题）。

七、实战案例：递归解决'汉诺塔'问题

7.1 问题描述

汉诺塔（Hanoi）是经典递归问题：有 3 根柱子（A、B、C）和 n 个大小不同的圆盘，初始时所有圆盘按从小到大顺序叠在 A 柱，要求将所有圆盘移动到 C 柱，移动规则：

1. 每次只能移动 1 个圆盘
2. 大盘不能放在小盘上面

7.2 递归思路

• 终止条件：n=1 时，直接将圆盘从 A 柱移动到 C 柱。
• 递归表达式：
  1. 将 n-1 个圆盘从 A 柱通过 C 柱移动到 B 柱（借助辅助柱 C）。
  2. 将第 n 个圆盘（最大圆盘）从 A 柱移动到 C 柱。
  3. 将 n-1 个圆盘从 B 柱通过 A 柱移动到 C 柱（借助辅助柱 A）。

7.3 代码实现

#include <iostream>
using namespace std;

// 汉诺塔递归函数：将 n 个圆盘从 from 柱通过 aux 柱移动到 to 柱
void hanoi(int n, char from, char aux, char to) {
    // 终止条件：n=1，直接移动
    if (n == 1) {
        cout << "移动圆盘 1 从 " << from << " 到 " << to << endl;
        return;
    }
    // 1. 移动 n-1 个圆盘从 from 到 aux（借助 to）
    hanoi(n - 1, from, to, aux);
    // 2. 移动第 n 个圆盘从 from 到 to
    cout << "移动圆盘 " << n << " 从 " << from << " 到 " << to << endl;
    // 3. 移动 n-1 个圆盘从 aux 到 to（借助 from）
    hanoi(n - 1, aux, from, to);
}

int main() {
    int n = 3; // 3 个圆盘（可修改为任意正整数）
    cout << "汉诺塔移动步骤（" << n << "个圆盘）：" << endl;
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

7.4 运行结果（n=3）

汉诺塔移动步骤（3 个圆盘）：
移动圆盘 1 从 A 到 C
移动圆盘 2 从 A 到 B
移动圆盘 1 从 C 到 B
移动圆盘 3 从 A 到 C
移动圆盘 1 从 B 到 A
移动圆盘 2 从 B 到 C
移动圆盘 1 从 A 到 C

结论：递归完美贴合汉诺塔的问题逻辑，代码简洁且易于理解，若 n 不大（如 n≤20），递归实现完全可行；若 n 极大（如 n>100），可将递归转换为迭代（手动维护栈存储移动状态）。

八、总结

1. 递归函数的核心是'分而治之'，需满足终止条件、递归表达式、收敛性三大要素。
2. 递归适用于树/图遍历、组合排列、数学问题等具有自相似性的场景，代码简洁但可能存在栈溢出、重复计算问题。
3. 尾递归可通过编译器优化为迭代，避免栈溢出，但依赖编译器支持，跨平台场景需谨慎使用。
4. 实际开发中，需根据问题规模、性能要求选择递归或迭代，必要时通过记忆化优化提升递归效率。