数据结构与算法 / 系统课时
递归的组成结构
递归的组成结构
递归把一个问题改写为规模更小的同类问题,并依靠调用返回逐层合并结果。本课用阶乘示例拆解基本情况、规模缩减和递归返回,帮助你判断一个递归函数是否能够正确终止。
学习目标
- 识别递归函数中的基本情况、递归步骤和返回合并。
- 按调用顺序追踪参数变化与返回值传播。
- 编写一个能够终止且结果正确的递归函数。
问题背景或应用场景
树遍历、分治算法和回溯搜索都需要重复处理结构相似的子问题。递归适合表达这类定义,但它并不是“函数调用自己”这么简单:缺少终止条件会无限深入,规模没有缩小也无法靠近终点,返回阶段处理错误则会得到错误结果。
核心原理
一个完整递归通常包含三个相互配合的部分:
- 基本情况:在一个或多个可直接求解的输入处结束本分支。
- 规模缩减:把当前输入转换为更接近基本情况的输入。
- 返回合并:使用子问题的返回值构造当前问题的答案。

以阶乘为例,factorial(n) 在 n = 0 时返回 1;否则计算 n * factorial(n - 1)。对非负整数 n,每步保持参数合法并严格减一,所以数学过程会到达 0。Python 实际执行还受解释器递归深度和资源约束。递归调用先形成 4 → 3 → 2 → 1 → 0 的深入过程,随后返回值按相反方向逐层传播。
完整可运行示例
将下面代码保存为 recursive_structure.py。示例使用缩进打印调用深度,使进入递归和返回合并的顺序可见。
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}")运行命令如下:
python recursive_structure.py预期输出
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 = 24Tips
先写基本情况,再写递归步骤,可以迫使自己明确终止边界。给每次调用定义一个非负整数度量,确认每条递归分支都使度量严格减少,并写出基本情况。仅验证参数变小还不够,例如参数取正实数时反复除以 2 也永远不会恰好等于 0。
常见错误
最常见的问题是把基本情况写成 n == 1,却仍允许调用者传入 0。此时 0 会继续变成 -1、-2,递归无法终止。另一种错误是丢弃子问题结果,且当前分支没有返回值,从而返回 None。记录调用的缩进和结果是教学工具。深度增长时仅生成缩进的累计字符数就可能达到平方级,阶乘大整数转换也有额外成本。修复时应同时检查输入范围、终止条件和返回表达式。
本课练习
- 编写递归函数计算
1 + 2 + ... + n。要求拒绝负数输入,n = 0时返回0,并验证n = 5的结果为15。 - 编写递归函数统计字符串中某个字符出现的次数。每次只处理一个字符,并保证递归参数持续缩短;使用
"banana"和字符"a"验证结果为3。
本课总结
- 递归需要明确终止边界与递减度量。返回值型递归还要说明子问题结果如何构成当前结果。
- 调用阶段从大问题深入到最小问题,返回阶段按相反顺序构造答案。
- 判断能否终止的关键是证明每次调用都更接近基本情况。
下一课预告
下一课将学习“调用栈与递归成本”,把递归调用映射为栈帧,并分析递归深度为什么会直接影响辅助空间复杂度。