【算法】《算法图解》第三章学习笔记：递归的奥秘

前言

《算法图解》第三章为我们揭示了编程中一个强大且富有魅力的概念——递归（Recursion）。递归是一种解决问题的方法，它将问题分解为规模更小的相同问题，直到问题小到可以轻松解决。理解递归对于掌握更高级的算法（如快速排序、归并排序等）至关重要。本篇笔记将跟随书中的脚步，探索递归的原理、运作方式以及其在编程实践中的应用。

一、什么是递归

递归，简单来说，就是一个函数直接或间接调用自身的过程。书中用了一个生动的例子来解释：你找到一个上了锁的神秘手提箱，奶奶告诉你钥匙在另一个盒子里。你打开那个盒子，发现里面又是一个盒子… 这个寻找钥匙的过程，就是递归的体现——不断重复相同的动作（打开盒子），直到找到钥匙（达到某个终止条件）。

在编程中，递归函数会不断地调用自己，每次调用处理问题的一个更小的部分，直到达到一个无法再分解的”基本情况”。

二、递归函数的两个基本要素

每个递归函数都必须包含两部分，以确保其能正确执行并最终停止：

  1. 基线条件（Base Case）：这是递归函数停止调用自身并开始返回结果的条件。没有基线条件，递归函数就会无限地调用下去，直到耗尽所有内存（导致栈溢出）。基线条件是递归的出口。
  2. 递归条件（Recursive Case）：这是函数调用自身的部分。在递归条件中，函数会把问题分解成一个或多个规模更小的子问题，并对这些子问题进行递归调用。

（一）示例：倒计时函数

书中使用了一个简单的倒计时函数来说明这两个概念：

def countdown(i):
    print(i)
    if i <= 0:  # 基线条件：当i小于等于0时，停止递归
        return
    else:       # 递归条件：否则，继续调用自身，参数为i-1
        countdown(i - 1)

# 调用函数
countdown(5)
# 输出:
# 5
# 4
# 3
# 2
# 1
# 0

在这个例子中：

  • if i <= 0: 就是基线条件。当 i 减到0或以下时，函数打印数字后直接返回，不再调用 countdown。
  • else: countdown(i - 1) 就是递归条件。只要 i 大于0，函数就会调用自己，并传入一个更小的值 i-1，逐渐向基线条件靠近。

三、调用栈（The Call Stack）

计算机是如何跟踪递归函数中众多的函数调用的呢？答案是使用调用栈（Call Stack），也简称为”栈”。调用栈是一种后进先出（LIFO）的数据结构，用于存储函数调用时的信息（如局部变量、返回地址等）。

（一）调用栈的工作原理

  1. 压入（Push）：每当一个函数被调用时，计算机会在调用栈顶部创建一个新的”栈帧”（Stack Frame），用于存储该函数调用的所有局部变量和参数。这个过程称为压栈或入栈。
  2. 弹出（Pop）：当一个函数执行完毕并返回时，它的栈帧会从调用栈顶部被移除。这个过程称为弹栈或出栈。程序控制权返回到调用该函数的地方（即栈中下一个栈帧所代表的函数）。

（二）递归与调用栈示例：阶乘

以计算阶乘的递归函数为例：

def fact(x):
    if x == 1:  # 基线条件
        return 1
    else:       # 递归条件
        return x * fact(x - 1)

result = fact(3)
print(result) # 输出: 6

当调用 fact(3) 时，调用栈的变化大致如下（简化表示）：

  1. fact(3) 被调用，fact(3) 的栈帧入栈。x=3。它需要计算 3 * fact(2)。
  2. fact(2) 被调用，fact(2) 的栈帧入栈（位于 fact(3) 之上）。x=2。它需要计算 2 * fact(1)。
  3. fact(1) 被调用，fact(1) 的栈帧入栈（位于 fact(2) 之上）。x=1。遇到基线条件，返回 1。
  4. fact(1) 的栈帧出栈。fact(2) 接收到返回值 1，计算 2 * 1 = 2，然后返回 2。
  5. fact(2) 的栈帧出栈。fact(3) 接收到返回值 2，计算 3 * 2 = 6，然后返回 6。
  6. fact(3) 的栈帧出栈。result 得到最终值 6。

每个 fact 函数调用都有自己独立的 x 变量，这些变量存储在各自的栈帧中，互不干扰。

四、递归的优缺点及与循环的对比

（一）优点

  • 代码简洁明了：对于某些类型的问题，特别是那些可以自然地分解为较小子问题的问题（如树的遍历、分治算法），递归可以使解决方案非常直观和易于理解。
  • 强大的表达能力：递归能够清晰地表达一些复杂的逻辑，用循环来实现可能会非常冗长和难以理解。

（二）缺点

  • 性能开销：每次函数调用都有一定的开销（如创建栈帧、参数传递等）。对于深度递归，这种开销累积起来可能相当可观，通常递归比等效的循环要慢。
  • 栈溢出（Stack Overflow）：如果递归深度太深（即函数调用自身次数太多），调用栈可能会耗尽所有可分配的内存空间，导致程序崩溃。这是递归最常见的问题之一。

（三）递归 vs. 循环

《算法图解》中提到一句经典的话：”如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。“

  • 迭代（循环）：通常效率更高，内存占用固定，不易出现栈溢出。但对于某些复杂问题，循环的逻辑可能难以构造和理解。
  • 递归：代码更接近人类思考方式，对于某些问题（如分治）更自然。但有性能和栈溢出的风险。

在实践中，很多递归算法都可以用迭代的方式重写，反之亦然。有些语言支持尾递归优化（Tail Call Optimization），可以将某些特定形式的递归（尾递归）转化为迭代，从而避免栈溢出的问题，并提高性能。但Python默认不支持尾递归优化。

五、一个经典的递归例子：计算阶乘

上面在解释调用栈时已经用到了阶乘的例子，这里再次完整展示：

def factorial(n):
    """计算一个非负整数n的阶乘"""
    if n < 0:
        return "阶乘只对非负整数定义"
    elif n == 0:  # 基线条件1：0的阶乘是1
        return 1
    elif n == 1:  # 基线条件2：1的阶乘是1 （这个基线条件可以合并到n==0，或作为主要基线）
        return 1
    else:         # 递归条件：n! = n * (n-1)!
        return n * factorial(n - 1)

# 测试
print(f"5! = {factorial(5)}")  # 输出: 5! = 120
print(f"0! = {factorial(0)}")  # 输出: 0! = 1
print(f"-2! = {factorial(-2)}") # 输出: -2! = 阶乘只对非负整数定义

这个阶乘函数清晰地展示了递归的两个核心：

  1. 基线条件：当 n 为0或1时，直接返回1。
  2. 递归条件：当 n 大于1时，函数调用自身计算 (n-1)!，然后乘以 n。

六、总结

递归是一种强大的编程范式，它通过函数调用自身来解决问题。理解递归的关键在于掌握它的两个基本组成部分：基线条件和递归条件。调用栈是实现递归的底层机制，它负责管理函数调用过程中的状态。虽然递归在某些情况下可能带来性能问题或栈溢出的风险，但其代码的简洁性和表达力使其在许多算法设计中不可或缺。选择递归还是循环，往往需要在代码可读性和程序性能之间做出权衡。

七、参考资料