C++函数的嵌套调用和递归调用学习教程

前言函数调用是 C 里最普通的动作一个函数在执行过程中调用另一个函数被调用的函数还可以继续调用别的函数这叫嵌套调用nested call。如果函数直接或间接地调用了自己就叫递归调用recursive call。两者在语法上没有特殊之处编译器也不需要额外的关键字真正需要理解的是调用发生时的栈帧stack frame变化以及递归必须满足的条件。初学者常见的误解有这几个。第一把「嵌套调用」和「递归调用」混为一谈——嵌套调用是 A 调 B、B 调 C调用链有限递归是调用链在同一个函数上重复必须有终止条件。第二认为递归一定比循环慢。递归确实有函数调用的开销但现代编译器在内联和小函数优化上可能把简单递归展开反过来某些问题树的遍历、分治用递归表达更清晰强行改写成迭代反而容易出错。第三认为「尾递归一定会被优化成循环」。C 标准不保证尾调用优化tail call optimization是否优化取决于编译器和优化选项不能把正确性建立在它上面。本文先讲调用栈再讲递归的两个必要条件然后用几个经典例子对比递归与迭代最后列出实际编码中的坑。示例以 C17 为基准只使用标准库。一、调用栈与嵌套调用每次函数调用发生时运行时会在调用栈上为这次调用分配一块区域通常称为栈帧。栈帧里保存返回地址、函数参数、局部变量以及需要保存的寄存器状态。函数返回时栈帧被弹出控制权回到返回地址处。嵌套调用的过程就是一串栈帧的压入与弹出。以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())这样的表达式C17 起两个实参的求值互不交错indeterminately sequenced但谁先谁后并未规定。如果g和h都修改同一个全局变量结果依赖求值顺序这类代码不应该写。二、递归的两个必要条件写递归只要盯住两件事缺一不可基线条件base case在什么情况下不再递归直接返回结果。递归步recursive step把原问题变成规模更小的同类问题并且每次都能向基线条件靠近。以阶乘为例n! n * (n-1)!是递归步0! 1! 1是基线。以二分查找为例基线是「区间为空」或「找到目标」递归步是把区间折半。缺少基线条件会无限递归最终栈溢出基线条件写错例如永远到不了同样如此。递归的调用链和嵌套调用没有本质区别只是同一段代码反复压栈。以factorial(4)为例栈会依次压入factorial(4)、factorial(3)、factorial(2)、factorial(1)到达基线后开始逐层返回每一层用自己的n乘以下一层的返回值。因此递归的执行分为「递」和「归」两个阶段很多错误就出在只想了「递」没想「归」。递归深度直接对应栈深度。处理深度由外部输入决定的递归例如解析任意嵌套的表达式、遍历深度未知的树时必须要么限制深度、要么改用显式栈的迭代写法否则恶意或异常输入可能把栈打穿。三、递归与迭代的对比维度递归迭代代码结构贴近数学定义分治类问题更直观需要自己维护状态空间开销每层一个栈帧通常 O(1) 额外空间时间开销有调用与返回的开销循环开销更小深度限制受栈大小限制不受调用栈限制尾递归标准不保证优化天然等价于循环调试调用栈清晰但层数多时难跟单步直观选择的原则不是「递归高级」或「循环快」而是问题本身是不是递归结构。树的遍历、汉诺塔、快速排序的分区、回溯搜索用递归写出来与定义几乎一一对应而线性累加、数组遍历这类问题循环更直接也没有栈溢出风险。如果递归存在大量重复子问题典型是朴素斐波那契可以用记忆化memoization把结果缓存下来把指数级复杂度降到线性。这本质上是用空间换时间缓存容器可以是std::vector或std::unordered_map。四、完整示例代码下面的例子覆盖嵌套调用、线性递归、带缓存的递归、递归二分查找和汉诺塔。// 适用于 C17#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_castunsigned long long(n) * factorial(n - 1);}// ---------- 记忆化递归 ----------unsigned long long fib(unsigned n,std::vectorunsigned 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::vectorint 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::vectorunsigned long long memo(91, 0);std::cout fib(90, memo) \n;const std::vectorint data{1, 3, 5, 7, 9, 11};std::cout binary_search(data, 7, 0,static_castint(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 工具链未做编译验证实际使用时请以自己的编译器为准。常见坑点❌ 递归函数忘记写基线条件或基线条件永远不成立。✅ 先写基线并单独测试再写递归步确保每次递归都让参数向基线靠近。❌ 朴素递归求斐波那契return fib(n-1) fib(n-2);复杂度 O(2 的 n 次方)重复计算大量子问题。✅ 加记忆化缓存或直接改成自底向上的迭代。❌ 递归函数按值接收大容器int search(std::vectorint v, ...)每层都复制一份。✅ 用const std::vectorint只在需要修改副本时才按值传递。❌ 递归里依赖全局变量或static局部变量保存中间状态函数不可重入、多线程下数据竞争。✅ 把状态作为参数或返回值显式传递或封装成对象成员。❌ 认为「尾递归一定会被编译器优化成循环」于是用深递归处理大输入。✅ 不依赖尾调用优化深度可能很大时改成显式栈的迭代写法。❌ 递归深度由外部输入决定且不设上限超深输入导致栈溢出。✅ 加深度上限并在超限时返回错误或改用迭代。❌ 递归函数某条分支忘记return函数走到末尾却没有返回值非void函数是 UB。✅ 打开-Wall -Wextra//W4让编译器提示并保证每条路径都有返回。❌ 返回递归过程中局部变量的引用或指针调用结束后对象已销毁。✅ 返回值语义的对象或用std::unique_ptr明确所有权。总结概念关键点常见错误嵌套调用调用链有限每层独立栈帧按值传大对象递归基线必须存在且可达漏写或写错递归步规模必须缩小参数不变导致死递归递归深度受栈大小限制不设上限尾递归标准不保证优化当作必然优化记忆化缓存重复子问题的结果缓存越界嵌套调用理解栈帧就够了递归则要同时盯住「基线」和「规模递减」两个条件。把递归当成一种描述问题的结构而不是一种性能技巧选择起来就不会纠结。