什么是阶乘？
在数学中，一个正整数n的阶乘（表示为n!）是所有小于及等于n的正整数的积。
阶乘的数学定义：
n! = n × (n-1) × (n-2) × ... × 3 × 2 × 1
例如：5! = 5 × 4 × 3 × 2 × 1 = 120
特别地，数学上规定0! = 1，这是阶乘函数的一个特殊情况。
递归函数的概念
递归是一种编程技巧，函数在执行过程中调用自身。递归函数通常包含两个关键部分：
- 基准条件（Base Case）：递归终止的条件，防止无限递归
- 递归条件（Recursive Case）：函数调用自身的条件
递归特别适合解决可以分解为相似子问题的问题，阶乘计算就是这类问题的典型例子。
Python递归实现阶乘
下面是使用递归实现阶乘计算的Python代码：
def factorial(n):
# 基准条件：0! 和 1! 都等于1
if n == 0 or n == 1:
return 1
# 递归条件：n! = n * (n-1)!
else:
return n * factorial(n-1)
# 测试阶乘函数
print(factorial(5)) # 输出: 120
print(factorial(0)) # 输出: 1
print(factorial(7)) # 输出: 5040
代码解析
- 基准条件：当 n 为 0 或 1 时，直接返回 1（0! = 1, 1! = 1）
- 递归条件：对于 n > 1，返回 n 乘以 (n-1) 的阶乘
- 每次递归调用都会减少 n 的值，直到达到基准条件
递归过程可视化
让我们以计算5!为例，分解递归调用的每一步：
factorial(5) = 5 × factorial(4)
↓
factorial(4) = 4 × factorial(3)
↓
factorial(3) = 3 × factorial(2)
↓
factorial(2) = 2 × factorial(1)
↓
factorial(1) = 1
↑
2 × 1 = 2
↑
3 × 2 = 6
↑
4 × 6 = 24
↑
5 × 24 = 120
递归过程分为两个阶段：递推阶段（分解问题直到基准条件）和回归阶段（将结果组合返回）。
递归的注意事项
递归深度限制
Python默认的递归深度限制是1000层。当递归深度超过此限制时，会引发RecursionError异常。
例如，尝试计算factorial(2000)会导致递归深度超出限制。
负数阶乘
数学上，负数没有阶乘定义。如果传入负数，我们的函数会无限递归直到达到最大递归深度。
改进后的阶乘函数应该包含输入验证：
def safe_factorial(n):
if n < 0:
raise ValueError("阶乘未定义负数")
if n == 0 or n == 1:
return 1
return n * safe_factorial(n-1)
递归与迭代的比较
| 特性 | 递归方法 | 迭代方法 |
|---|---|---|
| 代码简洁性 | 更简洁，接近数学定义 | 需要循环控制变量 |
| 性能 | 函数调用开销大，较慢 | 更快，无函数调用开销 |
| 内存使用 | 需要维护调用栈，内存占用高 | 内存占用低 |
| 适用场景 | 问题可自然分解为子问题 | 需要高性能的场景 |
迭代实现阶乘的示例：
def iterative_factorial(n):
result = 1
for i in range(1, n+1):
result *= i
return result
发表评论