掌握Python递归算法（从零开始学递归函数设计与实战）

第一个递归例子：计算阶乘

阶乘是学习递归的经典入门案例。例如，5! = 5 × 4 × 3 × 2 × 1 = 120。

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

在这个例子中，factorial(5) 会调用 factorial(4)，然后调用 factorial(3)……直到调用 factorial(1)，这时满足基础情况，开始逐层返回结果。

第二个例子：斐波那契数列

斐波那契数列定义为：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)（n≥2）。这也是一个典型的递归算法实例。

def fibonacci(n):    # 基础情况    if n == 0:        return 0    elif n == 1:        return 1    # 递归情况    else:        return fibonacci(n - 1) + fibonacci(n - 2)# 测试函数print(fibonacci(6))  # 输出: 8

注意：虽然这个实现简洁明了，但对于较大的 n 值效率较低（存在大量重复计算）。在实际项目中，我们常使用“记忆化”或动态规划优化，但这超出了本教程范围。

递归的优缺点

优点：

• 代码简洁、逻辑清晰，尤其适合树形结构或分治问题。
• 能自然地表达某些数学定义（如阶乘、斐波那契）。

缺点：

• 递归深度过大可能导致栈溢出（RecursionError）。
• 某些情况下效率不如迭代（循环）实现。

小贴士：如何写出正确的递归函数？

1. 先明确问题的最小规模（即基础情况）。
2. 思考如何将当前问题转化为更小规模的同类问题。
3. 确保每次递归调用都向基础情况靠近，避免无限递归。

通过本教程，你已经掌握了Python递归算法的基本原理和两个经典递归算法实例。继续练习更多题目（如汉诺塔、二叉树遍历），你会越来越熟练！记住，对Python初学者递归来说，理解比死记更重要。希望这篇递归函数教程对你有所帮助！