Python 递归函数

在 Python 中，如果一个函数在其函数体内部调用该函数的本身，这样的函数就叫做 “递归函数（recursive function）”。

Python 递归函数的原理就是，使用一个函数通过不断地调用函数自身，从而循环地处理数据。直到处理到最后一步，再将每一步的计算结果向上一步逐级返回。递归函数的原理如下图所示。

特别注意，在使用 Python 递归函数的过程中一定要有结束递归的判断条件，否则递归会无限制地执行下去，造成死循环，直到程序报错。

递归函数实现 “n 的阶乘”

我们先来看一个最简单的例子，那就是使用 Python 递归函数来实现 n 的阶乘。

示例 1：n 的阶乘

# 定义函数
def multi(n):
    if n == 1:
        return 1
    else:
        return n * multi(n - 1)

# 调用函数
print(multi(3))

运行结果如下。

6

分析：

上面示例定义了一个名为 “multi” 的函数，由于该函数内部使用了函数本身，所以它是一个递归函数。multi() 函数满足下面的递归关系。这种递归关系，表示的是 1~n 的乘积可以由 n 乘以 1~n-1 的乘积计算得到。如果 n 等于 1，则可以直接得到结果。

使用递归函数 multi() 来计算 3 阶乘，也就是执行 multi(3)，需要以下几步：

• 第 1 步：multi(3) 等价于 3 * multi(3 - 1)，也就是执行 3 * multi(2)，此时等待 multi(2) 返回结果。
• 第 2 步：multi(2) 等价于 2 * multi(2 - 1)，也就是执行 2 * multi(1)，此时等待 multi(1) 返回结果。
• 第 3 步：对于 multi(1) 来说，此时 n 等于 1，返回结果为 1，然后就会将结果返回第 2 步。第 2 步拿到了 multi(1) 的返回值，就可以计算得到 multi(2) 的结果，也就是 2 * 1 = 2。最后把 multi(2) 的结果返回给第 1 步，就可以计算得到 multi(3) 的结果，也就是 3 * 2 = 6。

需要特别注意的是，递归一定要有一个退出条件，否则就会一直递归下去。对于上面这个例子来说，它的递归退出条件就是 n == 1。

递归函数实现 “斐波那契数列”

知道递归函数怎么使用之后，再来看一个经典的递归实例：斐波那契数列。斐波那契数列，又称 “黄金分割数列” 或 “兔子数列”，它指的是这样一个数列：0、1、1、2、3、5、8、13、21、34……。对于斐波那契数列，它从第 3 项开始，每一项都等于前两项之和，所以满足下面的公式。

接下来尝试使用 Python 递归函数的方式来求出斐波那契数列前 20 项数字（从 0 项开始），并且将结果保存到一个列表里面去。

示例 2：斐波那契数列

# 定义函数，获取第 n 个数
def fibonacci(n):
    if n < 2:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

result = []
for i in range(20):
    result.append(fibonacci(i))
print(result)

运行结果如下。

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

分析：

在上面示例中，我们定义了一个名为 “fibonacci” 的函数，该函数是一个递归函数。对于 fibonacci() 函数来说，它递归的退出条件为 n < 2。

实际上，递归函数并没有想象中那么复杂，我们只需要把递归的条件找出来，然后在函数体内根据一定的规则不断调用函数本身就可以了。

Python 递归函数的优缺点

对于递归函数来说，它有以下的优点。

• 简洁性：递归函数可以使用较少代码来实现复杂功能。
• 问题分解：递归函数可以将复杂任务分为为更简单的子任务。
• 可读性高：递归可以更直观地表示问题的解决方案，特别对于涉及嵌套结构的问题。

同时，递归函数也有以下的缺点。

• 逻辑复杂：某些情况下，递归背后的逻辑很难理解。
• 时间和空间消耗大：递归函数由于是函数调用自身，执行效率低下，会占用大量内存。
• 难以调试：递归函数很难调试。