一文搞懂递归函数

# 前言

递归是学习任何一门语言都绕不过去的一道坎，平时都习惯使用迭代循环去实现，初看递归总是要想一会儿才能理解，然而过一阵子又忘记怎么写了。

# 概念

在函数内部，可以调用其它函数，也可以调用自身，如果在函数内部调用自身，这个函数就是递归函数。

它主要包含两个阶段：

1. 递：程序不断深入的调用自身，通常传入更小或更简化的参数，直到达到“终止条件”。
2. 归：触发“终止条件”后，程序从最深层的递归函数开始逐层返回，汇集每一层的结果。

而从实现的角度看，递归代码主要包含三个要素。

1. 终止条件：用于决定什么时候由“递”转“归”。
2. 递归调用：对应“递”，函数调用自身，通常输入更小或更简化的参数。
3. 返回结果：对应“归”，将当前递归层级的结果返回至上一层。

观察一下代码，我们只需要调用函数recur(n)，就可以完成 1 x 2 x 3 x ... x n 的阶乘计算：

def recur(n: int) -> int:
    """递归"""
    # 终止条件
    if n == 1:
        return 1
    # 递：递归调用
    res = recur(n-1)
    # 归：返回结果
    return n * res

下图展示了该函数的递归过程。

--插入图片--

虽然从计算角度看，迭代与递归可以得到相同的结果，但它们代表了两种完全不同的思考和解决问题的方式。

• 迭代：“自下而上”地解决问题，从最基础的步骤开始，然后不断重复或累加这些步骤，知道任务完成。
• 递归：“自上而下”地解决问题，将原问题分解为更小的子问题，这些子问题和原问题具有相同的形式。接下来将子问题继续分解为更小的子问题，直到基本情况时停止（基本情况的解是已知的）。

以上述阶乘函数为例，设问题f(n) = 1 x 2 x 3 x ... x n。

• 迭代：在循环中模拟乘积的过程，从 1 遍历到 n ，每轮执行乘积操作，即可求得f(n)。
• 递归：将问题分解为子问题f(n) = n * f(n-1)，不断递归分解下去，直到基本情况f(1) = 1时终止。

# 调用栈

递归函数每次调用自身时，系统都会为新开启的函数分配内存，以存储局部变量、调用地址和其他信息等。这将导致两方面的结果。

• 函数的上下文数据都存储在称为“栈帧空间”的内存区域中，直至函数返回后才会被释放。因此，递归通常比迭代更加消耗内存空间。
• 递归调用函数会产生额外的开销。因此递归通常比循环的时间效率更低。

如下图所示，在出发终止条件前，同事存在 n 个未返回的递归函数，递归深度为 n。

--插入图片--

在实际中，编程语言允许的递归深度通常是有限的，过深的递归可能会导致栈溢出错误。可以试试调用recur(1000):

>>> recur(1000)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 7, in recur
  File "<stdin>", line 7, in recur
  File "<stdin>", line 7, in recur
  [Previous line repeated 995 more times]
  File "<stdin>", line 4, in recur
RecursionError: maximum recursion depth exceeded in comparison

# 尾递归

有趣的是，如果函数在返回前的最后一步才进行递归调用，则该函数可以被编译器或解释器优化，使其在空间效率与迭代相当。这种情况被称为尾递归，递归调用栈溢出可以通过尾递归优化解决。

• 普通递归： 当函数返回上一层的函数后，需要继续执行代码，因此系统需要保存上一层调用的上下文。
• 尾递归： 递归调用时函数返回前的最后一个操作，这意味着函数返回到上一层级后，无法继续执行其他操作，因此系统无须保存上一层函数的上下文。

还是以计算1 x 2 x 3 x ... x n 为例，我们可以将结果变量 res 设为函数参数，从而实现尾递归：

def tail_recur(n: int, res: int = 1) -> int:
    """尾递归"""
    # 终止条件
    if n == 1:
        return res
    # 尾递归调用
    return tail_recur(n-1, res * n)

尾递归的执行过程如下所示，对比普通递归和尾递归，两者的乘积操作的执行点是不同的。

• 普通递归：乘积操作是在“归”的过程中执行的，每层返回后都要执行一次乘积操作。
• 尾递归：求和操作实在“递”的过程中执行的，“归”的过程只需层层返回。

--插入图片--

# 小结

递归函数的优点是逻辑简单清晰，缺点是过深的调用会导致栈溢出。

迭代的效率通常较高，无函数调用开销，而递归每次函数调用都会产生开销。

针对尾递归优化的语言可以通过尾递归防止栈溢出。

Python标准解释器没有针对尾递归做优化，任何递归函数都有存在栈溢出的问题。