c++怎么实现递归算法_c++阶乘计算实例【基础】

递归函数必须有明确终止条件，否则会无限调用导致栈溢出；如阶乘中n==0或n==1是必要出口，常见错误是终止条件遗漏（如只写n==2而忽略n==1）或条件不全。

递归函数必须有明确的终止条件

没有终止条件的递归会无限调用自身，最终导致栈溢出（Stack overflow）。比如计算阶乘时，n == 0 或 n == 1 就是必须写的出口。

常见错误是把终止条件写成 n == 2 却忘了处理 n == 1，或者用 n 但没考虑负数输入——c++ 不会自动拦截负数，得靠逻辑判断或断言。

• 推荐统一用 n == 0 作为基础情形（因为数学上定义 0! = 1）
• 如果参数类型是 unsigned int，可省略负数检查；但若用 int，建议加 if (n 或抛异常
• 不要依赖编译器优化尾递归——标准 C++ 不保证尾递归优化，gcc -O2 可能生效，但不可移植

阶乘递归实现要小心整型溢出

int 在大多数平台最多表示到 12!（479001600），13! 就溢出了；long long 也只撑到 20!（约 2.4e18）。这不是递归本身的问题，而是数值范围限制。

示例代码：

立即学习“C++免费学习笔记（深入）”；

long long factorial(int n) {     if (n < 0) return -1;     if (n == 0 || n == 1) return 1;     return n * factorial(n - 1); }

• 别用 float 或 double 做阶乘——精度丢失快，且不能准确表示大整数
• 真要算大数阶乘，得换高精度库（如 boost::multiprecision）或手写数组模拟
• 编译时加 -ftrapv（GCC/Clang）可捕获有符号整数溢出，方便调试

递归调用开销比循环大，小数据看不出，大数据明显

每次递归都压栈：保存返回地址、局部变量、寄存器状态。对阶乘这种线性递归，时间和空间复杂度都是 O(n)，但常数因子比迭代高一截。

对比迭代写法：

long long factorial_iter(int n) {     if (n < 0) return -1;     long long result = 1;     for (int i = 2; i <= n; ++i)         result *= i;     return result; }

• 实测 n = 10000 时，递归版大概率栈溢出，迭代版稳稳运行
• 递归更贴近数学定义，适合教学和逻辑清晰的场景；工程中优先考虑迭代，除非问题天然具有分治结构（如快速排序、树遍历）
• 某些编译器在 -O2 下会对简单尾递归做优化，但别依赖——C++ 标准不强制要求

递归看起来简洁，但栈深度、溢出、性能这三块最容易被忽略，尤其初学时只盯着“函数调自己”这个形式，而忘了它背后是实实在在的内存和 CPU 操作。