一起动脑筋 · 先看一个小故事
女孩想数一叠卡片：拿走一张后，剩下的仍是一叠卡片。能不能把同样的问题交给下一次自己？
把过程摊开来看
- 数 3 张1 加上数 2 张
- 数 2 张1 加上数 1 张
- 数 0 张返回 0
- 逐层返回1、2、3
递归用同一种方法解决更小的同类问题，再把结果带回来。
每次调用有自己的任务，不是所有层共用一份计数。必须知道什么时候不用再往下分。
看见调用，也看见返回
任务卡从左到右表示从栈底到栈顶。最右边是当前正在执行的一层。
f(3)
这一层要算 3 × f(2)，先等待 f(2)。
f(3) 等待f(2)
这一层要算 2 × f(1)，再新增一层。
f(3) 等待f(2) 等待f(1) 等待f(0) = 1
f(0) 直接返回 1，不再新增调用。
f(3) 等待f(2) 等待f(1) = 1
计算 1 × 1，得到 1 并返回。
f(3) 等待f(2) = 2
计算 2 × 1，得到 2 并返回。
f(3) = 6
计算 3 × 2，得到 6。本次调用完成。
01递归到底是什么？
递归（Recursion）是一种解决问题的方法：
把一个问题变成一个更小但结构相同的问题，不断缩小，直到遇到可以直接解决的情况。
较大的问题→更小的同类问题→可以直接解决
02递归代码通常有什么两部分？
基本情况
什么时候可以直接得到答案，不再继续调用。
递归情况
怎样把当前问题缩小，再交给下一层。
03一个最小的递归例子
void printDown(int n) {
if (n == 0) {
return;
}
std::cout << n << '\n';
printDown(n - 1);
}这里：
n == 0是基本情况printDown(n - 1)是递归调用
04为什么 n - 1 很重要？
因为它让问题逐步变小：
n=3→n=2→n=1→n=0
最终一定能到达基本情况。
05递归只是“自己调用自己”吗？
不够准确。
如果只有“自己调用自己”，但没有缩小问题 + 到达基本情况，那只是无限调用，并不是一个正确的递归算法。
06递归一定比循环好吗？
不一定。
有些问题用循环更简单，有些问题的结构天然适合递归，例如树、分治、回溯。
你已经知道了什么
- 递归会把问题转化成规模更小的同类问题。
- 递归通常包含基本情况和递归情况。
- 问题规模必须不断接近基本情况。
- 只有“函数调用自己”还不够构成正确递归。
- 递归不一定比循环更好，要看问题结构。
下一篇：递归为什么一定要有停止条件？
轮到你来试一试
数卡片时每次递归仍传入 3，而不是 2，会接近结束吗？
想好了吗？点开看解释
不会。参数没有朝终止条件变化，会不断新增调用，最终可能耗尽调用栈。