Factorial
非负整数 n 的阶乘记作 n!，它是从 1 到 n 的所有整数的乘积。例如，4! = 1 × 2 × 3 × 4 = 24。根据定义，0! = 1。你的函数接收 n，并返回 n!。
函数
- ninteger
- 你要计算阶乘的那个整数
- 返回值integer
- 从 1 到 n 的每个整数的乘积；当 n 为 0 时，乘积为 1
约束条件
0 ≤ n ≤ 12- 答案可以用有符号 32 位整数表示：最大的数是
12! = 479001600。
示例
- 输入
- n = 5
- 输出
- 120
- 解释
- 计算
1 × 2 × 3 × 4 × 5。累乘结果依次为 1、2、6、24，最终得到 120。
- 输入
- n = 0
- 输出
- 1
- 解释
- 没有可相乘的数，而没有因子的乘积是
1。这就是为什么0! = 1。
进阶
100! 有 158 位。你能不计算它，数出它末尾有多少个零吗？
提示
逐个打开提示，每个都会多透露一点。
把
4!和5!写成乘积。5!和4!有什么关系？5! = 5 × 4!。一般来说，n! = n × (n-1)!，这个链条会在0! = 1处结束。将乘积初始值设为
1，再将它乘以从2到n的每个数字。初始值设为 1，也能得到0和1的正确结果。
题解
阶乘有两种等价的描述方式，而且每种都能写成代码。作为乘积，n! = 1 × 2 × ... × n 是一个循环。作为递归定义，0! = 1 和 n! = n × (n-1)! 表示一个会调用自身的函数。两种方式都要进行大约 n 次乘法；循环不需要调用栈。
从定义理解递归
思路
如果你知道 4! = 24，那么 5! = 5 × 24 = 120。所以，factorial(n) 会调用 factorial(n-1)，并将返回的答案乘以 n。基本情况 factorial(0) 不需要调用其他函数，直接返回 1。从 5 开始，调用会依次向下到 5、4、3、2、1、0，然后答案依次返回：1、1、2、6、24、120。
总共有 n + 1 次调用和 n 次乘法：时间复杂度为 O(n)。每次调用都会在调用栈中等待它下面的调用完成，因此栈中会有 n + 1 个栈帧，空间复杂度为 O(n)。
算法
- 如果
n是0，返回1。这是基本情况。 - 否则，对
n-1调用函数。 - 将结果乘以
n并返回。
def factorial(n):
if n == 0:
return 1 # base case: 0! = 1
return n * factorial(n - 1)在循环中相乘
思路
将递归展开为一个不断累乘的过程：从 result = 1 开始，乘以 2，然后乘以 3，依此类推，直到 n。从 1 开始也能处理 n = 0 和 n = 1：从 2 到 n 的循环会运行 0 次，并返回 1，这两种情况的答案都是对的。
这需要进行 n-1 次乘法，时间复杂度为 O(n)，并且只使用一个数字，空间复杂度为 O(1)，不会有调用栈溢出的风险。
算法
- 将
result = 1。 - 让
k从2循环到n，包括两端。 - 每一步都将
result乘以k。 - 返回
result。
def factorial(n):
result = 1
for k in range(2, n + 1):
result *= k
return result
易错点和边界情况
- 将乘积的初始值设为
0。每次乘法都会让它保持为 0，所以初始值应设为1。 - 只在
n == 1时停止递归。调用函数时如果参数是0，函数会继续递归到 -1、-2，依此类推，直到栈溢出。应将n == 0设为基本情况。 - 使用
k < n而不是k ≤ n进行循环。这会漏掉最后一个因子，所以输入5时结果是 24，而不是 120。 - 在 Swift 中写
for k in 2...n。当n为 0 或 1 时，结束值小于起始值的闭区间会在运行时崩溃。
常见问题3
计算阶乘的时间复杂度是多少？
循环和递归都会对不超过 n 的每个数字进行一次乘法：时间复杂度为 O(n)。循环只需要 O(1) 的额外空间。递归会为每次调用保留一个栈帧，直到返回基准情况，因此需要 O(n) 的空间。
为什么 0! 等于 1？
0! 表示没有任何数相乘，而没有因子的乘积是 1，就像没有任何项相加时，和是 0 一样。这样还能让 n! = n × (n-1)! 在 n = 1 时成立。而且，排列 0 个物品恰好只有一种方式。
能放进整数的最大阶乘是多少？
12! = 479001600 是能存入有符号 32 位整数的最大阶乘。20! = 2432902008176640000 是能存入有符号 64 位整数的最大阶乘。超过这个范围，你就需要使用大小不受限制的数字类型，例如 Python 的 int、Java 的 BigInteger 或 JavaScript 的 BigInt。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def factorial(n):
# 在这里编写代码测试 #1
测试 #2
参数
n = 5
预期输出
120