一起动脑筋 · 先看一个小故事
3 个不同玩具排成一行有多少种顺序？第一个位置有 3 种选择，后面还有 2 和 1 种。
把过程摊开来看
- 3!3 乘 2!
- 2!2 乘 1!
- 1!1 乘 0!
- 0! = 1返回后得 1、2、6
阶乘 n! 表示从 1 乘到 n，约定 0! = 1。
递归写成 n! = n × (n−1)!，每次把任务缩小一层。3! 的返回结果是 6。
看见调用，也看见返回
任务卡从左到右表示从栈底到栈顶。最右边是当前正在执行的一层。
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什么是阶乘？
正整数阶乘写作 n!：
4! = 4 × 3 × 2 × 1 = 24
数学上规定：
0! = 1
02阶乘为什么天然有递归结构？
因为：
n! = n × (n - 1)!
比如：
4!=4 × 3!=4 × 3 × 2!
03递归代码怎样写？
long long factorial(int n) {
if (n == 0) {
return 1;
}
return n * factorial(n - 1);
}这里假设输入 n >= 0。
04factorial(4) 怎样向下调用？
factorial(1)factorial(2)factorial(3)factorial(4)
继续到 factorial(0) 后，不再递归，直接返回 1。
05答案怎样一层层算回来？
0! = 1↑1! = 1 × 1 = 1↑2! = 2↑3! = 6↑4! = 24
06为什么不能忽略输入范围？
如果传入负数，上面的函数会继续变成 -1、-2、-3……永远到不了 0。
所以真实程序要先规定函数的有效输入，或者主动检查。
07long long 能算很大的阶乘吗？
也不能无限大。
常见 64 位 long long 最多只能安全表示到 20!；21! 已经超过有符号 64 位整数最大范围。
08阶乘一定要用递归吗？
不一定，也可以用循环：
long long result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}阶乘主要用来帮助学习递归结构，并不表示递归一定是最合适的实现。
你已经知道了什么
- 阶乘满足
n! = n × (n-1)!。 0! = 1可以作为基本情况。- 递归调用逐层减小 n，返回时逐层相乘。
- 函数必须考虑有效输入范围。
- 阶乘增长非常快，即使 long long 也很快溢出。
- 阶乘也可以用循环实现。
下一篇：用递归解决“小问题里的小问题”
轮到你来试一试
为什么把 0! 写成 0 会把后面的答案都算错？
想好了吗？点开看解释
因为每层都乘上下一层，乘到 0 后结果都成为 0。正确的乘法起点是 1。