在 C++ 中，递归调用指函数在自身函数体内直接或间接调用自身。递归适合处理树形结构、深度优先搜索、分治算法等具备自相似特征的问题，代码往往比迭代方案更贴近问题描述。但是递归并非没有代价，每次函数调用都会在进程调用栈上产生新的栈帧，用于保存返回地址、寄存器状态、函数形参和局部变量。如果递归层数过多，或者每一层分配的局部空间过大，程序就可能因为栈空间耗尽而崩溃。因此 C++ 递归调用需要从终止条件、栈帧开销、重复计算等几个方面进行控制。
一、终止条件必须放在函数入口处，并保证可到达
写递归函数时最容易犯的错误是终止条件写在了递归调用之后，或者判断条件使用了永远无法满足的表达式。例如一个计算阶乘的函数，如果先调用 factorial(n - 1) 再判断 n 是否等于 1，调用根本不会执行到判断逻辑，而是不断向下递归。正确做法是在函数开始时先判断最小规模输入，再执行递归分支。
终止条件还要考虑边界输入。比如计算斐波那契数时，如果只判断 n == 1 就直接递归，当传入 0 或负数时会出现死循环或未定义行为。通常需要同时处理 n == 0 和 n == 1，或者对非法输入做断言。下面这个阶乘示例把终止条件放在首位，并且对负数做了保护。
long long factorial(int n) {
if (n < 0) {
return -1; // 非法输入保护
}
if (n <= 1) {
return 1; // 终止条件必须先判断
}
return n * factorial(n - 1);
}终止条件必须保证递归能逐步向它收敛。如果参数变化方向与目标相反，例如递归调用时参数递增而终止条件要求参数小于某个值，递归深度也会失控。可以把递归函数理解为一个状态转移过程，只有每层调用都使问题规模更接近基础情况，递归链才能在有限步内结束。
二、栈帧分配会放大内存占用，警惕栈溢出
递归调用使用的空间并不只取决于参数和返回值。每次进入函数时，编译器会在栈上为局部变量预留空间，包括局部数组、std::string 对象、std::vector 对象等。即使单个局部变量很小，深层递归也可能把空间消耗放大到几倍甚至几十倍。例如在递归函数中定义一个 int buffer[4096]，每层至少占用 16KB 栈空间，如果递归 1000 层，仅这一项就会消耗 16MB，而很多平台的默认线程栈大小只有 1MB 到 8MB。
不同类型的局部变量对栈帧大小影响差异很大。标量类型如 int、double、指针通常只占几个字长；但局部大数组、结构体、部分标准库容器会把栈帧迅速撑大。如果容器内部还要从堆上分配内存，栈帧本身虽然不存放元素数据，但对象指针、大小、容量等元信息仍然要占空间。下面这段代码在递归中声明固定大小数组，递归深度较大时非常危险。
#include <iostream>
void dangerousRecursion(int depth) {
int buffer[8192]; // 每层约 32KB 栈空间
if (depth == 0) {
std::cout << "done" << std::endl;
return;
}
dangerousRecursion(depth - 1);
}
int main() {
dangerousRecursion(10000); // 很可能触发栈溢出
return 0;
}即使算法逻辑正确，递归深度受限于可用栈空间。Windows 程序默认栈大小通常是 1MB，Linux 主线程默认栈大小常见为 8MB，具体受线程创建方式影响。对于不可控的外部输入，比如用户传入一个极大整数作为递归深度，或者树的深度可能接近节点总数，直接递归并不可靠。此时可以估算最坏深度与单层栈帧大小，评估是否突破限制。也可以通过 ulimit 或编译器选项调整栈大小，但这属于临时缓解而非根本解决，尤其不适用于库代码。
三、重复计算会导致指数级时间增长
递归调用如果只是简单把大问题拆成多个子问题，但子问题之间存在大量重叠，就会出现重复计算。最经典的例子是斐波那契数列：fib(n) = fib(n - 1) + fib(n - 2)。直接按这个公式递归，fib(5) 会重复计算 fib(3) 两次，fib(2) 三次，整体时间复杂度接近 O(2^n)。当 n 为 50 时计算已经非常缓慢。
解决重复计算通常有两种方式：记忆化搜索和动态规划。记忆化搜索保留递归结构，但用数组或哈希表存储已经求过的结果，函数入口先查表，命中则直接返回。下面的例子对比了普通递归和记忆化搜索。
#include <unordered_map>
long long fib(int n) {
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2); // 指数级重复计算
}
std::unordered_map<int, long long> memo;
long long fibMemo(int n) {
if (n <= 1) {
return n;
}
auto it = memo.find(n);
if (it != memo.end()) {
return it->second;
}
long long result = fibMemo(n - 1) + fibMemo(n - 2);
memo[n] = result;
return result;
}记忆化搜索的难点是缓存键设计和缓存清理。参数维度较高时，可以使用 std::map 或自定义哈希结构，但缓存本身也会占用内存，并且多次递归调用中的查找操作会引入额外开销。对于参数范围连续且有限的情况，使用 std::vector 比哈希表更高效。需要注意的是，记忆化只能消除重叠子问题，不能减少递归深度本身，所以如果递归深度仍然过大，还需配合其他手段。
四、尾递归优化不可依赖，必要时改成迭代
尾递归是指递归调用是函数最后一条语句，且返回值直接来自该递归调用，不再参与后续运算。例如计算阶乘的尾递归版本把中间结果放入参数累加：
long long factorialTail(int n, long long acc) {
if (n <= 1) {
return acc;
}
return factorialTail(n - 1, acc * n);
}理想情况下，编译器可以将尾递归优化为循环，复用当前栈帧，避免每层调用都分配新栈帧。但 C++ 标准并没有强制要求编译器进行尾调用优化。GCC 和 Clang 在开启 -O2 或 -O3 时通常能对简单尾递归做优化，MSVC 则不一定。因此不能把程序正确性建立在必然发生尾递归优化之上。如果代码必须保证不会栈溢出，应当直接写成迭代形式，或使用显式栈模拟递归。
将递归改成显式栈迭代可以保留递归思路，同时避免调用栈增长。以二叉树的深度优先遍历为例，递归版本依赖系统调用栈，而迭代版本可以使用 std::stack 保存待访问节点。下面是一个后序遍历的显式栈实现，它没有使用系统递归，遍历深度可以远超线程栈限制。
#include <vector>
#include <stack>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
};
void postorderIterative(TreeNode* root, std::vector<int>& result) {
std::stack<TreeNode*> stk;
TreeNode* lastVisited = nullptr;
TreeNode* current = root;
while (current != nullptr || !stk.empty()) {
if (current != nullptr) {
stk.push(current);
current = current->left;
} else {
TreeNode* top = stk.top();
if (top->right != nullptr && top->right != lastVisited) {
current = top->right;
} else {
result.push_back(top->val);
lastVisited = top;
stk.pop();
}
}
}
}迭代版本虽然代码更长，但栈空间使用更可控，因为 std::stack 默认使用双端队列，底层通常从堆上分配内存，不会直接消耗线程栈。判断递归是否值得保留，可以从输入规模、单层栈帧大小、代码可读性三个角度考虑。处理小规模输入或树形结构时递归通常简洁清晰；处理外部输入规模不可控、局部对象较大或要求高性能时，应优先考虑迭代或手动管理栈。
递归并不是 C++ 中需要被彻底避免的特性，关键是避免无界递归、控制单层空间占用、识别重复计算。写递归函数时先明确基础情况和参数收敛方向，再决定是否需要记忆化或改写为迭代。对于大多数业务逻辑，递归深度通常比较小，直接使用递归并不会引发问题；但在库函数、服务器请求处理或算法竞赛中，任何来自外部的数据都可能让递归深度迅速膨胀，必须在设计阶段就做好防护。