数据结构与算法 / 系统课时

递归的组成结构

递归的组成结构

递归把一个问题改写为规模更小的同类问题,并依靠调用返回逐层合并结果。本课用阶乘示例拆解基本情况、规模缩减和递归返回,帮助你判断一个递归函数是否能够正确终止。

学习目标

  • 识别递归函数中的基本情况、递归步骤和返回合并。
  • 按调用顺序追踪参数变化与返回值传播。
  • 编写一个能够终止且结果正确的递归函数。

问题背景或应用场景

树遍历、分治算法和回溯搜索都需要重复处理结构相似的子问题。递归适合表达这类定义,但它并不是“函数调用自己”这么简单:缺少终止条件会无限深入,规模没有缩小也无法靠近终点,返回阶段处理错误则会得到错误结果。

核心原理

一个完整递归通常包含三个相互配合的部分:

  1. 基本情况:在一个或多个可直接求解的输入处结束本分支。
  2. 规模缩减:把当前输入转换为更接近基本情况的输入。
  3. 返回合并:使用子问题的返回值构造当前问题的答案。

递归函数从调用到返回的三段结构

以阶乘为例,factorial(n) 在 n = 0 时返回 1;否则计算 n * factorial(n - 1)。对非负整数 n,每步保持参数合法并严格减一,所以数学过程会到达 0。Python 实际执行还受解释器递归深度和资源约束。递归调用先形成 4 → 3 → 2 → 1 → 0 的深入过程,随后返回值按相反方向逐层传播。

完整可运行示例

将下面代码保存为 recursive_structure.py。示例使用缩进打印调用深度,使进入递归和返回合并的顺序可见。

python
def factorial(n: int, emit=print) -> int:
    if type(n) is not int or n < 0:
        raise ValueError("n 必须是非负整数")

    def visit(value, depth):
        indent = "  " * depth
        emit(f"{indent}enter factorial({value})")
        if value == 0:
            emit(f"{indent}base case -> 1")
            return 1
        sub_result = visit(value - 1, depth + 1)
        result = value * sub_result
        emit(f"{indent}return {value} * {sub_result} = {result}")
        return result

    return visit(n, 0)

if __name__ == "__main__":
    answer = factorial(4)
    print(f"result = {answer}")

运行命令如下:

bash
python recursive_structure.py

预期输出

text
enter factorial(4)
  enter factorial(3)
    enter factorial(2)
      enter factorial(1)
        enter factorial(0)
        base case -> 1
      return 1 * 1 = 1
    return 2 * 1 = 2
  return 3 * 2 = 6
return 4 * 6 = 24
result = 24

Tips

先写基本情况,再写递归步骤,可以迫使自己明确终止边界。给每次调用定义一个非负整数度量,确认每条递归分支都使度量严格减少,并写出基本情况。仅验证参数变小还不够,例如参数取正实数时反复除以 2 也永远不会恰好等于 0。

常见错误

最常见的问题是把基本情况写成 n == 1,却仍允许调用者传入 0。此时 0 会继续变成 -1、-2,递归无法终止。另一种错误是丢弃子问题结果,且当前分支没有返回值,从而返回 None。记录调用的缩进和结果是教学工具。深度增长时仅生成缩进的累计字符数就可能达到平方级,阶乘大整数转换也有额外成本。修复时应同时检查输入范围、终止条件和返回表达式。

本课练习

  1. 编写递归函数计算 1 + 2 + ... + n。要求拒绝负数输入,n = 0 时返回 0,并验证 n = 5 的结果为 15。
  2. 编写递归函数统计字符串中某个字符出现的次数。每次只处理一个字符,并保证递归参数持续缩短;使用 "banana" 和字符 "a" 验证结果为 3。

本课总结

  • 递归需要明确终止边界与递减度量。返回值型递归还要说明子问题结果如何构成当前结果。
  • 调用阶段从大问题深入到最小问题,返回阶段按相反顺序构造答案。
  • 判断能否终止的关键是证明每次调用都更接近基本情况。

下一课预告

下一课将学习“调用栈与递归成本”,把递归调用映射为栈帧,并分析递归深度为什么会直接影响辅助空间复杂度。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

递归的组成结构

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通