跳到主要内容

Python 递归

提示
  1. Python递归的基础：递归是函数自我调用的过程，类似于两面镜子相对造成的无限反射。
  2. 递归函数示例：以阶乘函数为例，展示了递归如何通过逐步减少数值来简化问题。
  3. 递归的利弊：虽然递归可以简化代码和解决复杂问题，但可能导致逻辑难以理解和效率低下。

递归是用自身定义自身的过程。

一个现实世界的例子是将两面平行镜子相对放置。任何放在它们之间的物体都会被递归地反射。

Python递归函数​

在Python中，我们知道一个函数可以调用其他函数。函数甚至可以调用自己。这种结构被称为递归函数。

下面的图片展示了一个名为recurse的递归函数的工作原理。

Python递归函数

以下是一个递归函数的例子，用来查找一个整数的阶乘。

一个数的阶乘是从1到该数的所有整数的乘积。例如，6的阶乘（表示为6!）是1*2*3*4*5*6 = 720。

递归函数的例子​

def factorial(x):
    """这是一个递归函数
    用来查找一个整数的阶乘"""

    if x == 1:
        return 1
    else:
        return (x * factorial(x-1))

num = 3
print("The factorial of", num, "is", factorial(num))

输出

3的阶乘是6

在上面的例子中，factorial()是一个递归函数，因为它调用了自己。

当我们用一个正整数调用这个函数时，它会通过递减的方式递归地调用自己。

每个函数都会将数字与它下面的数的阶乘相乘，直到它等于1。这个递归调用可以用以下步骤解释。

factorial(3) # 第1次调用，传入3
3 * factorial(2) # 第2次调用，传入2
3 * 2 * factorial(1) # 第3次调用，传入1
3 * 2 * 1 # 从第3次调用返回，因为数字=1
3 * 2 # 从第2次调用返回
6 # 从第1次调用返回

让我们来看一个展示递归过程的逐步图片：

通过递归方法求阶乘

我们的递归在数字减少到1时结束。这被称为基础条件。

每个递归函数都必须有一个停止递归的基础条件，否则函数会无限地调用自己。

Python解释器限制了递归的深度，以帮助避免无限递归，从而导致堆栈溢出。

默认情况下，递归的最大深度是1000。如果超过限制，会导致RecursionError。让我们看一个这样的情况。

def recursor():
    recursor()
recursor()

输出

Traceback (most recent call last):
    File "<string>", line 3, in <module>
    File "<string>", line 2, in a
    File "<string>", line 2, in a
    File "<string>", line 2, in a
 [上一行重复了996次]
RecursionError: 超出了最大递归深度

递归的优点​

  1. 递归函数使代码看起来清洁且优雅。
  2. 使用递归可以将复杂任务分解为更简单的子问题。
  3. 使用递归生成序列比使用一些嵌套迭代更容易。

递归的缺点​

  1. 有时候递归背后的逻辑难以跟随。
  2. 递归调用开销大（效率低），因为它们占用了大量内存和时间。
  3. 递归函数难以调试。
最后于 更新