C++ · 函数
递归
用阶乘比较递归与循环，跟踪调用和返回过程，理解终止条件、调用栈空间及朴素斐波那契递归的重复计算。
终止条件与规模缩小
递归就像"俄罗斯套娃"：打开一个娃娃，里面还有一个更小的，直到最小那个打不开为止（终止条件）。
写递归必须回答两个问题：
① 什么时候停？（终止条件，也叫边界条件）
② 每次怎么变小？（递归关系，问题规模必须减小）
调用链：f(5) → f(4) → f(3) → f(2) → f(1)，到 f(1) 直接返回，然后一层层往回"收"答案。
递归与循环：阶乘的调用和返回
factorial(3) 依次调用 factorial(2)、factorial(1)，再返回 1→2→6。递归需要终止条件与规模缩小；循环可以直接保存当前乘积。
long long factorialIterative(int n) {
long long result = 1;
for (int i = 2; i <= n; ++i) result *= i;
return result;
}这里约定 0≤n≤20，结果可由 long long 表示。两种阶乘实现时间都是 O(n)；递归需要 O(n) 调用栈空间，循环只需 O(1) 辅助空间。不能假定编译器会消除递归。树形问题可能更适合递归表达，但朴素斐波那契递归会重复计算，不能把所有递归都看成线性时间。
先自己判断：n=0 时，循环一次也不执行，为什么仍返回正确结果？
初值是 1，符合 0!=1；如果把 result 初始化为 0，所有正整数阶乘也会算错。
阶乘与斐波那契的递归代码
例1：求 n 的阶乘
#include <iostream>
using namespace std;
// 约定 0 <= n <= 20；0! = 1
long long factorial(int n) {
if (n <= 1) return 1; // 终止条件
return n * factorial(n - 1); // 递归调用
}
int main() {
cout << factorial(5) << endl; // 输出 120
return 0;
}factorial(5)=5×factorial(4)=5×4×factorial(3)=…=5×4×3×2×1=120。每次 n 减 1，最终到 1 停下，再逐层把结果乘回去。
例2：斐波那契数列（第 n 项）
#include <iostream>
using namespace std;
// F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2)
int fib(int n) {
if (n == 1 || n == 2) return 1; // 终止条件
return fib(n - 1) + fib(n - 2);
}
int main() {
for (int i = 1; i <= 8; i++) {
cout << fib(i) << " ";
}
cout << endl; // 输出：1 1 2 3 5 8 13 21
return 0;
}fib(5)=fib(4)+fib(3)，fib(4)=fib(3)+fib(2)……一直拆到 fib(1) 或 fib(2) 就直接返回 1。注意这个写法会重复计算，n 较大时会很慢。
提示
- 递归必须有终止条件（基础情况），没有就会"爆栈"导致程序崩溃。
- 每次递归调用，问题规模一定要变小（如 n-1），不然永远到不了终止条件。
- 递归安全深度取决于运行环境和栈帧大小；深度过大时考虑循环或显式栈，记忆化不一定降低调用深度。
- 理解递归的关键：先想清楚"最小子问题怎么解"，再写"大问题如何依赖小问题"。
先修知识
技术参考
范围说明
本站讲解由 InfoCode 编写，不是官方考纲；参考级别是本站映射，不代表官方等级、认证或参赛资格。练习记录不等于掌握或资格。
参考级别：GESP 5 级（本站映射）