异常教程

Python 使用递归计算阶乘（长文讲解）

更新时间:

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

截止目前， 星球 内专栏累计输出 90w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 3100+ 小伙伴加入学习 ，欢迎点击围观

理解阶乘：数学基础与编程需求

阶乘（Factorial）是数学中一个基础概念，表示从1到某个正整数n的所有整数的乘积，记作n!。例如，5! = 5×4×3×2×1 = 120。在编程领域，阶乘的计算是学习算法和数据结构时的典型示例，尤其在递归算法的讲解中被广泛使用。

对于编程初学者而言，阶乘的计算看似简单，但其背后隐藏着重要的编程思想。例如，通过循环（Iteration）或递归（Recursion）两种方式实现，可以直观地对比程序设计的不同逻辑模式。本文将聚焦于Python 使用递归计算阶乘这一主题，结合代码示例和原理分析，帮助读者掌握递归的核心思想及其应用场景。

递归：程序设计中的“自我重复”

什么是递归？

递归（Recursion）是编程中一种函数调用自身的技巧，类似于数学归纳法的逻辑结构。想象一个“俄罗斯套娃”：最大的娃娃内部包含一个稍小的娃娃，而每个小娃娃都遵循相同的结构，直到最小的那个不再包含其他娃娃。递归的核心在于两点：

  1. 递归终止条件（Base Case）：明确何时停止递归调用，避免无限循环。
  2. 递归步骤（Recursive Step）：将问题分解为更小的子问题，通过调用自身解决这些子问题，最终合并结果。

递归的优缺点

优点缺点
代码简洁，逻辑直观可能导致栈溢出（Stack Overflow）
适用于天然递归结构的问题（如树、图遍历）性能开销较大，因函数调用频繁
提升问题分解的清晰度需谨慎设计终止条件

用递归实现阶乘：分步解析

阶乘的数学表达式与递归映射

阶乘的数学定义可表示为：
[ n! = \begin{cases}
1 & \text{当 } n = 0 \text{ 或 } n = 1 \
n \times (n-1)! & \text{当 } n > 1
\end{cases} ]

观察上述公式，可以发现：

  • 终止条件：当n为0或1时，结果直接为1。
  • 递归关系：当n>1时，n! 等于n乘以(n-1)!，而(n-1)! 又是一个更小的阶乘问题。

这与递归的逻辑完全吻合，因此可以通过递归轻松实现。

编写第一个递归函数

以下是用Python实现阶乘的递归版本：

def factorial_recursive(n):  
    """  
    使用递归计算阶乘  
    Args:  
        n (int): 非负整数  
    Returns:  
        int: n的阶乘  
    """  
    # 终止条件  
    if n == 0 or n == 1:  
        return 1  
    # 递归步骤  
    else:  
        return n * factorial_recursive(n - 1)

代码逐行解析

  1. 函数定义：factorial_recursive 接受参数n，返回其阶乘。
  2. 文档字符串：说明函数用途、参数和返回值，便于其他开发者理解。
  3. 终止条件：当n为0或1时，直接返回1。这是递归的“出口”，防止无限循环。
  4. 递归步骤：返回 n * factorial_recursive(n-1)，将问题规模缩小1，直到触发终止条件。

示例运行

print(factorial_recursive(5))  # 输出：120  
print(factorial_recursive(0))   # 输出：1

递归的执行过程：以n=5为例

为了理解递归如何逐步解决问题，我们可以手动模拟函数调用过程：

  1. 初始调用：factorial_recursive(5)

    • 条件判断：5 ≠ 0且5 ≠ 1 → 进入递归步骤。
    • 返回值：5 × factorial_recursive(4)

  2. 递归调用1：factorial_recursive(4)

    • 返回值：4 × factorial_recursive(3)

  3. 递归调用2：factorial_recursive(3)

    • 返回值：3 × factorial_recursive(2)

  4. 递归调用3：factorial_recursive(2)

    • 返回值：2 × factorial_recursive(1)

  5. 递归调用4：factorial_recursive(1)

    • 触发终止条件 → 返回1

  6. 回溯计算：

    • factorial_recursive(2) → 2 × 1 = 2
    • factorial_recursive(3) → 3 × 2 = 6
    • factorial_recursive(4) → 4 × 6 = 24
    • factorial_recursive(5) → 5 × 24 = 120

通过“递推”（进入递归）和“回溯”（返回结果）的过程，递归函数逐步解决了问题。

递归与循环的对比：两种思维模式

除了递归，阶乘也可以通过循环实现：

def factorial_iterative(n):  
    result = 1  
    for i in range(1, n+1):  
        result *= i  
    return result

对比分析

方面递归实现循环实现
代码简洁性更简洁，直接映射数学公式需要显式维护循环变量
性能可能因函数调用栈导致额外开销更高效，无函数调用的额外开销
可读性对数学背景强的开发者更直观对编程新手更友好
适用场景适合天然递归结构（如树、图）适合需要优化性能的场景

递归的潜在问题与优化策略

问题1：栈溢出（Stack Overflow）

Python默认的递归深度有限（通常为1000层）。尝试计算非常大的n（如factorial_recursive(10000)）时，会引发RecursionError。

解决方案：

  • 增加递归深度限制（不推荐，可能引发崩溃）： 
    import sys  
sys.setrecursionlimit(1500)  # 调整递归深度
  • 改用循环实现：避免栈溢出风险。

问题2：重复计算与性能

例如，计算factorial(5)时，factorial(4)、factorial(3)等会被多次调用。对于更复杂的递归问题（如斐波那契数列），这可能导致指数级时间复杂度。

优化方法：

  • 记忆化（Memoization）：缓存已计算的结果，避免重复计算。 
    def factorial_memo(n, memo={}):  
    if n in memo:  
        return memo[n]  
    if n == 0 or n == 1:  
        return 1  
    else:  
        result = n * factorial_memo(n-1)  
        memo[n] = result  
        return result

实际案例：阶乘在组合数学中的应用

阶乘常用于排列组合问题。例如，计算从n个不同元素中取出k个的排列数（Permutation）：

[ P(n, k) = \frac{n!}{(n-k)!} ]

使用递归阶乘函数可以快速实现：

def permutation(n, k):  
    return factorial_recursive(n) // factorial_recursive(n - k)  

print(permutation(5, 3))  # 输出：60（5×4×3）

总结与进阶建议

通过本文的讲解，读者可以掌握以下关键点：

  1. 递归的基本概念、结构及适用场景。
  2. 如何将数学问题（阶乘）转化为递归函数。
  3. 递归与循环的对比及性能优化策略。

对于希望深入学习的读者，建议：

  • 练习更多递归案例，如斐波那契数列、汉诺塔问题。
  • 学习尾递归优化（Tail Recursion）和动态规划（Dynamic Programming）等高级技巧。
  • 探索Python中functools.lru_cache装饰器实现记忆化。

掌握递归不仅是学习一种编程技巧，更是培养分治思想（Divide and Conquer）的重要途径。在解决问题时，尝试将大问题拆解为小问题，或许你会惊喜地发现，递归能带来意想不到的简洁与优雅！

最新发布

查看更多文章