递归是C++中常用的编程思路，适合处理分治、回溯、树形结构遍历等场景，但未经优化的递归很容易出现栈溢出、重复计算多、执行速度慢的问题。掌握合适的优化技巧，才能让递归在项目中稳定发挥作用。
递归常见的问题
在C++中使用递归时，最常见的问题主要有三类：一是递归深度过深导致调用栈溢出，比如计算较大的斐波那契数时，默认的栈空间无法承载过深的调用；二是重复计算严重，很多递归分支会重复计算相同的结果，浪费大量算力；三是函数调用开销大，每次递归调用都需要压栈出栈，频繁调用会拖慢整体执行速度。
常用优化技巧
1. 尾递归转换
尾递归指的是递归调用是函数执行的最后一个操作，编译器可以对尾递归做优化，复用当前栈帧而不是新增栈帧，避免栈溢出。以计算阶乘为例，普通递归和尾递归的对比如下：
// 普通递归计算阶乘，递归调用后还有乘法操作，不是尾递归
int factorial_normal(int n) {
if (n <= 1) return 1;
return n * factorial_normal(n - 1);
}
// 尾递归版本，递归调用是最后一步，传入累加参数acc记录中间结果
int factorial_tail(int n, int acc = 1) {
if (n <= 1) return acc;
return factorial_tail(n - 1, n * acc);
}如果编译器开启了尾递归优化，尾递归版本的阶乘可以支持更大的n值而不会出现栈溢出。
2. 递归剪枝
在回溯类递归场景中，很多分支是不符合要求的，提前判断并终止这些分支的递归，就是剪枝。比如求解组合总和问题时，当前和已经超过目标值就可以直接停止当前分支的递归：
#include <vector>
using namespace std;
vector<vector<int>> res;
vector<int> path;
void backtrack(vector<int>& candidates, int target, int start, int current_sum) {
// 剪枝：当前和已经超过目标，不需要继续递归
if (current_sum > target) return;
if (current_sum == target) {
res.push_back(path);
return;
}
for (int i = start; i < candidates.size(); i++) {
path.push_back(candidates[i]);
backtrack(candidates, target, i, current_sum + candidates[i]);
path.pop_back();
}
}剪枝可以大幅减少递归的调用次数，提升回溯逻辑的执行效率。
3. 递归缓存（记忆化）
对于有大量重复子问题的递归，比如斐波那契数列计算，可以用缓存存储已经计算过的结果，避免重复计算。C++中可以用unordered_map或者数组实现缓存：
#include <unordered_map>
using namespace std;
unordered_map<int, int> memo;
int fibonacci(int n) {
if (n <= 1) return n;
// 如果已经计算过，直接返回缓存结果
if (memo.find(n) != memo.end()) return memo[n];
int res = fibonacci(n - 1) + fibonacci(n - 2);
memo[n] = res;
return res;
}加入缓存后，斐波那契递归的时间复杂度从指数级降到了线性级，运行速度提升非常明显。
4. 迭代替代递归
如果递归逻辑可以用循环实现，优先用迭代替代递归，彻底避免栈溢出的问题。比如树的先序遍历，递归和迭代的实现对比如下：
#include <stack>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 递归先序遍历
void preorder_recursive(TreeNode* root, vector<int>& res) {
if (root == nullptr) return;
res.push_back(root->val);
preorder_recursive(root->left, res);
preorder_recursive(root->right, res);
}
// 迭代先序遍历，用栈模拟递归调用栈
void preorder_iterative(TreeNode* root, vector<int>& res) {
if (root == nullptr) return;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
res.push_back(node->val);
// 先压右子树，再压左子树，保证左子树先出栈
if (node->right) st.push(node->right);
if (node->left) st.push(node->left);
}
}迭代版本没有递归深度限制，适合处理节点数较多的树结构。
优化技巧选择建议
不同的递归场景适合不同的优化方式：如果是线性递归且编译器支持尾递归优化，优先用尾递归转换；如果是回溯类场景，优先加剪枝逻辑；如果有大量重复子问题，优先加缓存；如果递归逻辑简单可转循环，优先用迭代替代。实际开发中可以根据场景组合使用多种优化技巧，让递归代码既简洁又高效。