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

常见应用场景

递归的优势在于代码简洁、逻辑清晰，特别适合具有'自相似性'的问题。

数学问题求解

除了阶乘，斐波那契数列、幂运算（a^b = a × a^(b-1)）以及最大公约数（欧几里得算法）都是经典应用。

例如求最大公约数：

// 递归求 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;
}

数据结构遍历与操作

树的前序、中序、后序遍历，图的深度优先搜索（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);
}

组合与排列问题

子集生成、全排列、组合求和等问题通常使用回溯法（Backtracking），本质也是递归的一种变体。

常见问题与解决方案

栈溢出（Stack Overflow）

原因：递归深度过大导致栈帧耗尽，或缺少终止条件导致无限调用。

对策：

1. 控制递归深度，确保不超过栈限制。
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;
}

重复计算（效率低下）

部分递归（如斐波那契数列）会重复计算相同子问题，导致时间复杂度指数级增长。可通过记忆化搜索或动态规划解决。

记忆化优化示例：

#include <vector>

std::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;
    return 0;
}

未优化的 F(30) 需百万次调用，记忆化后仅需 30 次，效率提升显著。

尾递归与 C++ 中的优化

什么是尾递归

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

对比普通递归与尾递归：

// 普通递归：递归调用后需执行乘法运算
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); // 无额外计算
}

优化原理

普通递归每次调用都在栈上创建新栈帧，而尾递归允许编译器复用当前栈帧，仅更新参数，本质上等价于迭代，从而避免栈溢出。但需注意，C++ 标准未强制要求编译器实现尾递归优化，GCC/Clang 在开启 -O2 后支持较好，VS 支持相对有限。

使用注意事项

1. 显式开启优化：GCC/Clang 需通过 -O2 或 -O3 编译选项启用。
2. 确保末尾调用：递归调用后不能有表达式计算。
3. 累积器传递：通过参数存储中间结果。

若编译器不支持优化，尾递归仍可能溢出，跨平台场景下迭代仍是稳妥之选。

递归与迭代的选择策略

建议：

1. 优先递归：问题自相似性强，深度小，可读性优先。
2. 改用迭代：深度大（如 n>1000）、性能敏感、防溢出。
3. 折中方案：记忆化优化兼顾效率与可读性。

实战案例：汉诺塔

汉诺塔是经典递归问题。规则是将 n 个圆盘从 A 柱移至 C 柱，大盘不能压小盘。

思路：

1. 终止条件：n=1 时直接移动。
2. 递归表达式：
   • 将 n-1 个从 A 移到 B（借助 C）。
   • 将第 n 个从 A 移到 C。
   • 将 n-1 个从 B 移到 C（借助 A）。

代码实现：

#include <iostream>
using namespace std;

void hanoi(int n, char from, char aux, char to) {
    if (n == 1) {
        cout << "移动圆盘 1 从 " << from << " 到 " << to << endl;
        return;
    }
    hanoi(n - 1, from, to, aux);
    cout << "移动圆盘 " << n << " 从 " << from << " 到 " << to << endl;
    hanoi(n - 1, aux, from, to);
}

int main() {
    int n = 3;
    cout << "汉诺塔移动步骤（" << n << "个圆盘）：" << endl;
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

递归完美贴合汉诺塔逻辑，代码简洁。若 n 极大，可转为迭代手动维护栈。

总结

递归的核心是'分而治之'，需满足终止条件、递归表达式、收敛性三大要素。它适用于树/图遍历、组合排列等自相似场景，但存在栈溢出和重复计算风险。尾递归可借助编译器优化为迭代，但需谨慎对待跨平台兼容性。实际开发中，应根据问题规模与性能需求权衡选择，必要时结合记忆化技术提升效率。