前言

函数调用是 C++ 里最普通的动作：一个函数在执行过程中调用另一个函数，被调用的函数还可以继续调用别的函数，这叫嵌套调用（nested call）。如果函数直接或间接地调用了自己，就叫递归调用（recursive call）。两者在语法上没有特殊之处，编译器也不需要额外的关键字，真正需要理解的是调用发生时的栈帧（stack frame）变化，以及递归必须满足的条件。

初学者常见的误解有这几个。第一，把「嵌套调用」和「递归调用」混为一谈——嵌套调用是 A 调 B、B 调 C，调用链有限；递归是调用链在同一个函数上重复，必须有终止条件。第二，认为递归一定比循环慢。递归确实有函数调用的开销，但现代编译器在内联和小函数优化上可能把简单递归展开；反过来，某些问题（树的遍历、分治）用递归表达更清晰，强行改写成迭代反而容易出错。第三，认为「尾递归一定会被优化成循环」。C++ 标准不保证尾调用优化（tail call optimization），是否优化取决于编译器和优化选项，不能把正确性建立在它上面。

本文先讲调用栈，再讲递归的两个必要条件，然后用几个经典例子对比递归与迭代，最后列出实际编码中的坑。示例以 C++17 为基准，只使用标准库。

一、调用栈与嵌套调用

每次函数调用发生时，运行时会在调用栈上为这次调用分配一块区域，通常称为栈帧。栈帧里保存返回地址、函数参数、局部变量以及需要保存的寄存器状态。函数返回时，栈帧被弹出，控制权回到返回地址处。

嵌套调用的过程就是一串栈帧的压入与弹出。以max3调用max2为例：

main
└─ max3(a, b, c) 栈帧：a, b, c
└─ max2(a, b) 栈帧：a, b（实参的副本）
└─ 返回
└─ max2(结果, c) 栈帧：结果, c
└─ 返回

这个模型解释了几件事：

• 
  
• 函数的局部变量彼此独立。max2被调用两次，两次的形参是两份不同的对象，互不影响。
• 
  
• 按值传参意味着拷贝。传一个大对象（例如几万元素的std::vector）会给每一层调用都复制一份，嵌套越深、代价越大；能用const引用就用const引用。
• 
  
• 栈空间是有限的。嵌套层数极深时会耗尽栈空间，行为不是「返回一个错误」，而是栈溢出（stack overflow），通常直接崩溃。
• 
  

需要区分的是「调用顺序」和「求值顺序」。像f(g(), h())这样的表达式，C++17 起两个实参的求值互不交错（indeterminately sequenced），但谁先谁后并未规定。如果g和h都修改同一个全局变量，结果依赖求值顺序，这类代码不应该写。

二、递归的两个必要条件

写递归只要盯住两件事，缺一不可：

1. 
   
2. 基线条件（base case）：在什么情况下不再递归，直接返回结果。
3. 
   
4. 递归步（recursive step）：把原问题变成规模更小的同类问题，并且每次都能向基线条件靠近。
5. 
   

以阶乘为例，n! = n * (n-1)!是递归步，0! = 1! = 1是基线。以二分查找为例，基线是「区间为空」或「找到目标」，递归步是把区间折半。缺少基线条件会无限递归，最终栈溢出；基线条件写错（例如永远到不了）同样如此。

递归的调用链和嵌套调用没有本质区别，只是同一段代码反复压栈。以factorial(4)为例，栈会依次压入factorial(4)、factorial(3)、factorial(2)、factorial(1)，到达基线后开始逐层返回，每一层用自己的n乘以下一层的返回值。因此递归的执行分为「递」和「归」两个阶段，很多错误就出在只想了「递」没想「归」。

递归深度直接对应栈深度。处理深度由外部输入决定的递归（例如解析任意嵌套的表达式、遍历深度未知的树）时，必须要么限制深度、要么改用显式栈的迭代写法，否则恶意或异常输入可能把栈打穿。

三、递归与迭代的对比

选择的原则不是「递归高级」或「循环快」，而是问题本身是不是递归结构。树的遍历、汉诺塔、快速排序的分区、回溯搜索，用递归写出来与定义几乎一一对应；而线性累加、数组遍历这类问题，循环更直接，也没有栈溢出风险。

如果递归存在大量重复子问题（典型是朴素斐波那契），可以用记忆化（memoization）把结果缓存下来，把指数级复杂度降到线性。这本质上是用空间换时间，缓存容器可以是std::vector或std::unordered_map。

四、完整示例代码

下面的例子覆盖嵌套调用、线性递归、带缓存的递归、递归二分查找和汉诺塔。

// 适用于 C++17
#include <cstdint>
#include <iostream>
#include <vector>

// ---------- 嵌套调用 ----------
int max2(int a, int b) { return a > b ? a : b; }

int max3(int a, int b, int c) {
return max2(max2(a, b), c); // 两次嵌套调用，两个独立的栈帧
}

// ---------- 线性递归 ----------
unsigned long long factorial(unsigned n) {
if (n <= 1) return 1; // 基线条件
return static_cast<unsigned long long>(n) * factorial(n - 1);
}

// ---------- 记忆化递归 ----------
unsigned long long fib(unsigned n,
std::vector<unsigned long long>& memo) {
if (n < 2) return n; // 基线条件
if (memo[n] != 0) return memo[n]; // 命中缓存
memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
return memo[n];
}

// ---------- 递归二分查找 ----------
// 找不到返回 -1；调用方保证 v 已升序排列
int binary_search(const std::vector<int>& v, int target, int lo, int hi) {
if (lo > hi) return -1; // 基线：区间为空
const int mid = lo + (hi - lo) / 2; // 避免 lo + hi 溢出
if (v[mid] == target) return mid; // 基线：找到
if (v[mid] < target)
return binary_search(v, target, mid + 1, hi);
return binary_search(v, target, lo, mid - 1);
}

// ---------- 汉诺塔 ----------
void hanoi(int n, char from, char to, char via) {
if (n == 0) return; // 基线：没有盘子要移动
hanoi(n - 1, from, via, to); // 先把上面 n-1 个移到中转柱
std::cout << from << " -> " << to << '\n';
hanoi(n - 1, via, to, from); // 再把 n-1 个移到目标柱
}

int main() {
std::cout << max3(3, 9, 4) << '\n';
std::cout << factorial(10) << '\n';

std::vector<unsigned long long> memo(91, 0);
std::cout << fib(90, memo) << '\n';

const std::vector<int> data{1, 3, 5, 7, 9, 11};
std::cout << binary_search(data, 7, 0,
static_cast<int>(data.size()) - 1) << '\n';

hanoi(3, 'A', 'C', 'B');
return 0;
}

几点说明：

• 
  
• factorial用unsigned long long返回，但 21 的阶乘已经超出 64 位无符号整数的表示范围。无符号整数溢出在标准里是回绕（模 2 的幂），不是 UB，但结果没有数学意义。生产代码应改用任意精度库或提前检查上限。
• 
  
• fib(90)仍在unsigned long long范围内（第 90 项约 2.88e18，小于 1.8e19），但fib(93)会溢出。缓存容器的大小要覆盖所有可能的n，否则memo[n]越界是 UB。
• 
  
• 二分查找的mid = lo + (hi - lo) / 2比(lo + hi) / 2更稳妥，因为后者在lo与hi都接近int上限时会溢出，而有符号整数溢出是 UB。
• 
  
• 汉诺塔的移动次数是 2 的 n 次方减一，n 稍大输出就会非常长，示例只演示 n 为 3 的情况。
• 
  
• 这些代码都是按标准语义写的，本机没有 C++ 工具链，未做编译验证；实际使用时请以自己的编译器为准。
• 
  

常见坑点

1. 
   
2. ❌ 递归函数忘记写基线条件，或基线条件永远不成立。
3. 
   

✅ 先写基线并单独测试，再写递归步；确保每次递归都让参数向基线靠近。

1. 
   
2. ❌ 朴素递归求斐波那契：return fib(n-1) + fib(n-2);，复杂度 O(2 的 n 次方)，重复计算大量子问题。
3. 
   

✅ 加记忆化缓存，或直接改成自底向上的迭代。

1. 
   
2. ❌ 递归函数按值接收大容器：int search(std::vector<int> v, ...)，每层都复制一份。
3. 
   

✅ 用const std::vector<int>&，只在需要修改副本时才按值传递。

1. 
   
2. ❌ 递归里依赖全局变量或static局部变量保存中间状态，函数不可重入、多线程下数据竞争。
3. 
   

✅ 把状态作为参数或返回值显式传递，或封装成对象成员。

1. 
   
2. ❌ 认为「尾递归一定会被编译器优化成循环」，于是用深递归处理大输入。
3. 
   

✅ 不依赖尾调用优化；深度可能很大时改成显式栈的迭代写法。

1. 
   
2. ❌ 递归深度由外部输入决定且不设上限，超深输入导致栈溢出。
3. 
   

✅ 加深度上限并在超限时返回错误，或改用迭代。

1. 
   
2. ❌ 递归函数某条分支忘记return，函数走到末尾却没有返回值（非void函数是 UB）。
3. 
   

✅ 打开-Wall -Wextra//W4让编译器提示，并保证每条路径都有返回。

1. 
   
2. ❌ 返回递归过程中局部变量的引用或指针，调用结束后对象已销毁。
3. 
   

✅ 返回值语义的对象，或用std::unique_ptr明确所有权。

总结

嵌套调用理解栈帧就够了，递归则要同时盯住「基线」和「规模递减」两个条件。把递归当成一种描述问题的结构，而不是一种性能技巧，选择起来就不会纠结。