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

调用栈与递归成本

调用栈与递归成本

递归代码通常很短,但每次函数调用都要在调用栈中保存独立状态。本课通过递归求和统计调用次数和最大栈深度,并据此区分运行时间、递归深度与辅助空间复杂度,理解递归和循环实现的成本差异。

学习目标

  • 解释递归调用如何创建、保留和释放栈帧。
  • 根据最大递归深度判断辅助空间复杂度。
  • 比较线性递归与循环实现的时间、空间成本。

调用栈如何增长与回退

从调用模型看,每个尚未完成的调用都有一份逻辑帧,保存参数、局部状态和后续执行位置。解释器与编译器对物理栈和帧对象的实现可能不同。当前调用必须等待更深一层返回,因此这些栈帧会同时保留;当基本情况返回后,栈帧才按后进先出的顺序逐个释放。

以 recursive_sum(3) 为例,递归调用依次传入 3、2、1、0。到达基本情况时,已有四层调用尚未完成,递归栈深度达到最大值 4。随后最内层返回 0,外层依次计算 1 + 0 = 1、2 + 1 = 3、3 + 3 = 6,对应栈帧逐层释放。

递归调用栈的增长与回退

栈深度取决于同一时刻尚未返回的调用层数,而不是整个程序累计执行了多少次函数调用。对于线性递归,这两个数值可能相同;对于存在多个分支的递归,它们通常不同。

递归与循环的时间、空间成本

同一个问题既可以用递归实现,也可以用循环实现。两种写法可能具有相同的渐进时间复杂度,却消耗不同的辅助空间。分析递归时,如果只统计执行次数而忽略调用栈,就会低估内存成本和深层输入带来的失败风险。

对于从 n 递减到 0 的线性递归,共有 n + 1 次调用,最大同时存在 n + 1 个递归栈帧。若每层只做常数工作,且不考虑整数位宽增长带来的额外成本,则时间复杂度为 Θ(n),辅助空间复杂度也为 Θ(n)。

等价循环仍需执行 n 次迭代,但只保留固定数量的变量,因此辅助空间复杂度为 Θ(1)。这里的辅助空间指算法执行时额外使用的空间,不包括输入数据本身。

实现方式 工作次数 最大额外状态 时间复杂度 辅助空间复杂度
线性递归 n + 1 次调用 n + 1 个递归栈帧 Θ(n) Θ(n)
循环 n 次迭代 固定数量变量 Θ(n) Θ(1)

这里假设每个递归栈帧只保存常数规模的数据。如果每层额外创建长度与当前问题规模相关的列表或字符串,就需要进一步统计这些对象在递归过程中同时占用的空间,不能直接套用 Θ(n)。

用代码统计调用次数与递归深度

下面的程序使用 Python 3.9 或更高版本,同时计算递归版本和循环版本。stats 记录递归调用总数与最大深度,便于把抽象复杂度映射到可观察数据。

python
def recursive_sum(n: int, stats: dict[str, int], depth: int = 1) -> int:
    if n < 0:
        raise ValueError("n must be non-negative")

    # 每次进入函数统计一次调用,depth 表示当前递归层数。
    stats["calls"] += 1
    stats["max_depth"] = max(stats["max_depth"], depth)

    # 到达基本情况后,不再创建新的递归栈帧。
    if n == 0:
        return 0

    return n + recursive_sum(n - 1, stats, depth + 1)


def iterative_sum(n: int) -> int:
    if n < 0:
        raise ValueError("n must be non-negative")

    # 循环只更新固定数量的变量,不累积调用栈帧。
    total = 0
    for value in range(1, n + 1):
        total += value
    return total


if __name__ == "__main__":
    number = 5
    stats = {"calls": 0, "max_depth": 0}

    recursive_result = recursive_sum(number, stats)
    iterative_result = iterative_sum(number)

    print(f"recursive result = {recursive_result}")
    print(f"recursive calls = {stats['calls']}")
    print(f"maximum stack depth = {stats['max_depth']}")
    print(f"iterative result = {iterative_result}")

预期结果:当 number = 5 时,两种方法均得到 15。递归从 5 调用到 0,因此调用次数与统计得到的最大递归深度均为 6。

这里的 depth 是程序自行维护的计数器,只统计 recursive_sum 函数自身的活跃调用层数,不包含解释器、模块入口或其他外部函数的栈帧。它适合分析递归算法的空间增长趋势,但不是进程实际栈内存占用量。

运行与验证

将代码保存为 recursion_cost.py,在安装了 Python 3.9 或更高版本的环境中执行:

bash
python recursion_cost.py

预期输出:

text
recursive result = 15
recursive calls = 6
maximum stack depth = 6
iterative result = 15

两个结果相同,说明递归与循环实现了相同的求和功能。调用次数和最大深度均为 6,对应从 5 到 0 的六层递归调用。

可以进一步检查三个边界:

  • n = 0:递归执行一次并直接返回 0,最大深度为 1;循环不执行任何迭代。
  • n = 1:递归调用两次,最大深度为 2,两种实现都返回 1。
  • n < 0:两种实现都抛出 ValueError,避免递归继续向负数方向深入。

基本情况和每条分支的递减度量共同决定终止。对深度有界的递归,也仍需考虑具体运行环境的资源上限。

递归深度限制与常见误判

Python 默认设置递归深度限制,深层递归可能触发 RecursionError。例如,将 number 改成一个远大于默认递归限制的数值,递归版本可能在完成计算前失败,而循环版本没有相同的递归深度限制。

另一个常见误判是把尾递归直接视为 Θ(1) 空间。只有运行环境明确执行尾调用优化或尾调用消除时,尾递归才可能复用栈帧。Python 不保证尾调用消除,因此即使把递归调用放在函数返回位置,也不能据此认定其空间复杂度为 Θ(1)。

对于树形递归,还需要区分总调用次数和最大栈深度。例如,深度优先遍历包含 1000 个节点的平衡二叉树,虽然累计访问 1000 个节点,但沿单条递归路径同时保留的栈帧数量只与树高同阶,不必同时保留所有节点对应的调用帧。

分叉后调用次数和深度会分开

顺序遍历一棵高度为 h 的满层二叉树。程序按从根到叶的边数定义 h,根调用深度计作 1。每个内部调用先完整执行左分支,再执行右分支。

python
def count_complete_tree(height):
    """height 是根到叶的边数,height=0 表示只有一个节点。"""
    if type(height) is not int or height < 0:
        raise ValueError("height 必须是非负整数")
    calls = 0
    max_depth = 0

    def visit(remaining, depth):
        nonlocal calls, max_depth
        calls += 1
        max_depth = max(max_depth, depth)
        if remaining > 0:
            visit(remaining - 1, depth + 1)
            visit(remaining - 1, depth + 1)

    visit(height, 1)
    return calls, max_depth

print(count_complete_tree(3))

输出为 (15, 4)。访问次数为 2h+1−12^{h+1}-1,同时活跃深度为 h+1h+1。这两个计数都基于不创建树对象的访问示例。如果实现另外构造结果树或保存遍历序列,需单独计入相应空间。

动手验证与复杂度判断

  1. 将示例中的 number 改为 8,再次运行程序。递归调用次数和最大深度都应为 9,递归结果与循环结果都应为 36。解释为什么结果增加不意味着栈深度按同样比例增长。
  2. 编写递归函数计算列表最大值,要求空列表抛出异常,长度为 1 时直接返回唯一元素。使用索引传递当前位置,避免每层创建列表切片,并统计最大递归深度。假设每层只保存常数额外状态,分析其时间复杂度和辅助空间复杂度。

判断递归空间成本时,先找出最长的尚未返回的调用路径,再计算每层需要保留多少额外状态。对于本课的线性递归求和,时间复杂度与辅助空间复杂度都是 Θ(n);循环求和保持 Θ(n) 时间复杂度,同时将辅助空间降为 Θ(1)。

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

目录与阅读设置

阅读设置

17

记录一个想法

调用栈与递归成本

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

登录哪都通