T23：Python 递归

在此篇教程中，你将学习创建一个递归函数（一个调用自身的函数）。

 何为递归?

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法。

比如，一个物理世界的例子：放置两个相互面对的平行镜子，它们之间的任何对象都将被递归反射。

 递归函数

在 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(num, "的阶乘是:", factorial(num))

输出

3的阶乘是:6

分析

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

当我们用一个正整数传入参数给函数时，它会通过递减数字递归调用自己。

每个函数都将数字与其下方数字的阶乘相乘

如下图

，直到它等于 1。这个递归调用可以在以下步骤中解释。

factorial(3)          # 第一次调用 3
3 * factorial(2)      # 第二次调用 2
3 * 2 * factorial(1)  # 第三次调用 1
3 * 2 * 1             # 从第三次调用返回，number=1
3 * 2                 # 从第二次调用返回
6                     # 从第一次调用返回

让我们看下面的图片，它显示了递归函数程序运行的分步过程：

递归：阶乘函数的工作过程

当数字减少到 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. 递归函数很难调试。

转载请注明：XAMPP中文组官网 » [Python]函数⁽²³⁾|递归