Appearance

一文搞懂递归函数

geekbing2023-12-09Python递归函数

前言

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

概念

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

它主要包含两个阶段:

  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)

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

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

--插入图片--

TIP

遗憾额是,大多数编程语言并没有针对尾递归做优化,Python解释器也没有做优化,因此即使函数是尾递归形式,仍然可能会遇到栈溢出问题。

小结

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

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

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

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

上次更新 3/25/2024, 10:43:07 AM