Python 递归

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

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

你想正确学习递归吗？ 报名我们的 交互式递归课程。

Python 递归函数

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

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

以下是一个递归函数的示例，用于计算整数的阶乘。

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

递归函数示例

def factorial(x):
    """This is a recursive function
    to find the factorial of an integer"""

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


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

输出

The factorial of 3 is 6

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

当我们用一个正整数调用此函数时，它将通过递减该数来递归调用自身。

每个函数将该数与其下方数的阶乘相乘，直到等于一。此递归调用可以按以下步骤解释。

factorial(3)          # 1st call with 3
3 * factorial(2)      # 2nd call with 2
3 * 2 * factorial(1)  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

让我们看一张图片，展示正在发生的事情的逐步过程

代码可视化：想看看每个递归调用是如何执行的吗？试试我们逐行代码可视化工具。

当数字减小到 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
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

递归的优点

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

递归的缺点

1. 有时递归背后的逻辑很难理解。
2. 递归调用开销很大（效率低），因为它们占用大量内存和时间。
3. 递归函数很难调试。

另请阅读

• 使用递归求自然数之和的 Python 程序
• 使用递归显示斐波那契数列的 Python 程序
• Python if...else 语句

你想正确学习递归吗？ 报名我们的 交互式递归课程。