理解递归：从函数调用到逐层返回

递归的核心：解决同类型的子问题

递归（recursion）是一种解决问题的策略：把当前问题转化成一个或多个同类型的子问题，直到子问题能够直接解决。函数调用自身，是实现这种策略的常见方式，也称为直接递归；如果 A 调用 B、B 再调用 A，则形成间接递归。

可以沿着一条调用链，把过程理解为两个阶段：

1. 递：不断进入新的函数调用，通常处理更小或更简单的子问题，直到到达基础情形。
2. 归：当前调用结束后，返回调用者，恢复其执行；必要时组合子问题的结果。

三个要素：基础情形、递归调用与当前层的工作

基础情形不仅决定“什么时候停”，还要正确处理最简单的情况。需要返回答案的算法，应当给出这个最小问题的正确答案。

阶乘示例：把一部分计算交给下一层

阶乘满足：0! = 1；对于正整数，n! = n × (n − 1)!。下面假设 n 是非负整数。

求 factorial(3) 时，当前层知道自己的 n = 3，还需要获得 factorial(2) 的结果，才能完成乘法。函数先在递归调用处等待；收到返回值后，再执行 return n * result。

def factorial(n):
    if n == 0:
        return 1                      # Base case

    result = factorial(n - 1)         # Recursive call
    return n * result                 # Combine and return

print(factorial(3))  # 6

交互示例：调用栈如何增长与返回

每次调用都保留自己的参数和局部变量：第一层的 n 仍然是 3，下一层的 n 是 2。运行时通常通过调用栈（call stack）管理这些调用；每次调用对应一份执行状态，称为栈帧（stack frame），记录参数、局部变量以及返回后继续执行的位置。

拖动执行步骤，观察尚未结束的调用如何累积，又如何逐层返回。

到达 n = 0 时，这一层直接返回 1。随后 n = 1、n = 2、n = 3 各自完成剩余的乘法，依次返回 1、2、6。

递归与栈：保存尚未完成的工作

栈是一种后进先出（LIFO）的管理结构：新内容放到栈顶，称为入栈；取走栈顶的内容，称为出栈。栈顶是最近加入的内容，栈底是最早加入的内容。用于管理普通函数调用时，栈里保存一份份栈帧。

栈帧可以理解为“这一次函数调用的执行记录”。下面讨论普通 Python 函数的逻辑调用栈；具体内存布局由解释器实现决定。

Python 帧对象的 f_locals 提供局部变量信息，f_lasti 表示执行位置，f_back 指向调用者的帧。多层调用共享同一份函数代码，同时拥有各自的执行状态。

下面是把阶乘中的递归调用和乘法分开后的写法。在刚进入 factorial(0) 时，四次阶乘调用都尚未结束，各层已绑定的局部变量只有自己的 n。

此时 child 和 result 尚未赋值。最深层首先返回，上层才能获得 child，完成乘法，再返回给上一层。返回顺序来自嵌套的调用关系，正好符合后进先出规则。

def factorial(n):
    if n == 0:
        return 1

    child = factorial(n - 1)
    result = n * child
    return result

print(factorial(3))

第一句话：每次调用拥有自己的局部变量绑定

“建立新的局部变量表”可以理解为：每次调用都拥有独立的局部作用域和变量绑定，函数参数也属于局部变量。同名的 n 可以分别属于不同的调用。

例如调用下面的 show(2)，会进入 show(1)，再进入 show(0)。这三次调用分别保留：

返回时先打印 leave 0 call-0，再打印 leave 1 call-1，最后打印 leave 2 call-2。上层恢复执行时，仍然使用自己的 n 和 label。

这一规律也适用于普通的非递归函数调用。在这里，函数定义是一份，每次调用的执行状态分别建立。“局部变量表”是理解名称绑定的模型；解释器可以使用优化的局部变量存储，不必为每次调用实际分配一个普通 Python 字典。

def show(n):
    label = f"call-{n}"
    print("enter", n, label)
    if n > 0:
        show(n - 1)
    print("leave", n, label)

show(2)

局部变量独立，引用的对象仍然可以共享

独立的局部变量绑定并不意味着所有传入的数据都被复制。Python 参数绑定的是对象引用。下面每层都有自己的 n 和 items 绑定，但各层的 items 引用同一个列表。

第一层向列表加入 2，第二层向同一个列表加入 1。最终输出 [2, 1]，最外层的 values 也能看到这些修改。可以同时理解两件事：各层的局部名称分别管理；这些名称可以引用同一个可变对象。

def collect(n, items):
    if n == 0:
        return
    items.append(n)
    collect(n - 1, items)

values = []
collect(2, values)
print(values)

第二句话：返回后先完成当前语句

“先完成返回值的赋值”适用于 child = factorial(n - 1) 这样的赋值语句。更一般的规律是：子调用正常返回后，继续完成包含该调用的表达式或语句，再按控制流继续执行。

先看一个普通函数调用。执行 value = inner() 时，右侧必须先获得结果，才能把这个结果绑定到左侧的 value。因此输出顺序是 outer before、inner running、outer after 5。

1. outer() 打印 before，执行到赋值语句。
2. 开始执行 inner()；outer 等待，after 还没有执行。
3. inner 返回 5，outer 恢复，将 5 赋给自己的 value。
4. 赋值完成后，继续执行下一条 print。

递归遵循同一条规则，只是调用的函数仍然是自己。恢复时不会重新从函数第一行开始。

def inner():
    print("inner running")
    return 5

def outer():
    print("outer before")
    value = inner()
    print("outer after", value)

outer()

返回值怎么使用，取决于调用所在的表达式

所以，“从递归调用处恢复”描述的是控制流；“先赋值”描述的是特定语句的行为。下面给出两种阶乘写法：一种显式保存子结果，另一种直接把子结果用于乘法。两者对非负整数得到相同答案。

def factorial_named(n):
    if n == 0:
        return 1
    child = factorial_named(n - 1)
    return n * child

def factorial_inline(n):
    if n == 0:
        return 1
    return n * factorial_inline(n - 1)

print(factorial_named(3), factorial_inline(3))

第三句话：多个调用尚未结束，但上层在等待

“同时存在多次尚未结束的调用”，描述的是某一时刻调用状态的共存。在这里的单线程同步示例中，最深层正在执行，上层暂停等待。这不表示这些调用在并行计算。

下面的 total(n) 求从 0 到 n 的整数之和，假设 n 是非负整数。调用 total(2)，在刚进入 total(0) 时：

函数定义仍然只有一份，三次调用各有一份执行状态。调用者进入等待时，其调用并没有结束；它还欠着赋值、打印和加法这些后续工作。

可以把每个等待中的栈帧理解为一张保留的工作记录：“我自己的 n 是多少；我在等谁；对方结束后，我还要做什么。”下面的日志能同时观察局部变量保留、返回后的赋值，以及多层尚未结束的调用。

def total(n):
    print("enter", n)
    if n == 0:
        return 0
    child = total(n - 1)
    print("resume", n, child)
    return n + child

print("answer", total(2))

实际输出：逐层恢复使用各自的 n 和 child

上面的 total 示例实际输出如下。前三行表示进入三次调用；随后最深层返回，total(1) 先恢复，再由 total(2) 恢复。

resume 1 0 表示 total(1) 的 n 仍然是 1，child 已获得下一层返回的 0；它返回 1。resume 2 1 表示 total(2) 的 n 仍然是 2，child 已获得下一层返回的 1；它最终返回 3。

enter 2
enter 1
enter 0
resume 1 0
resume 2 1
answer 3

终止条件存在，还必须能够到达

阶乘函数虽然包含 n == 0，但如果传入 -1，后续参数会依次变成 -2、-3……，无法通过这个条件结束。因此，上面的非负整数输入约定很重要；工程代码应按接口契约校验输入。

正确的递归需要同时满足：

1. 存在可以直接处理的基础情形。
2. 对于允许的输入，每条递归路径都会在有限步内到达基础情形。

“参数变小”只是常见手段。真正需要保证的是剩余工作持续减少，并且能够结束。例如，遍历目录时可以递归进入子目录；如果把循环引用或符号链接也当作子目录跟随，就需要额外处理重复访问。

“归”可以执行动作，不必汇总数值

下面的例子没有组合数值结果，而是在进入和返回时分别打印。递归调用之前的代码随深入过程执行，递归调用之后的代码随返回过程执行。

调用 visit(3)，先输出 enter 3、enter 2、enter 1，再输出 leave 1、leave 2、leave 3。返回阶段继续做动作；在 Python 中，裸 return 或执行到函数末尾都会返回 None。

def visit(n):
    if n == 0:
        return

    print("enter", n)
    visit(n - 1)
    print("leave", n)

visit(3)

多分支递归会交替进入与返回

“递 → 归”的两阶段描述，最适合解释一条调用链。如果一个函数包含多个递归调用，例如依次遍历二叉树的左右子树，它可能先进入左子树、返回，再进入右子树、再次返回。整个执行过程会交替出现“递”和“归”。

理解递归代码时，可以逐层确认：这一层负责什么、把什么交给下一层、下一层结束后还剩什么工作。对于有多个子问题的算法，还要明确它们的执行顺序以及结果如何组合。

调用深度与可核验的依据

上层等待时，执行状态仍需保留。对于这个普通递归实现，调用越深，累积的状态越多。Python 设置了递归深度上限，可以通过 sys.getrecursionlimit() 查看当前值；即使算法逻辑能够终止，也可能在到达基础情形之前超过运行时允许的深度。

参考：Python 官方文档：函数调用的局部状态与 return ↗ · Python 官方文档：递归深度上限 ↗

进一步核验：Python 官方文档：帧对象及局部变量、执行位置、调用者关系 ↗ · Python 官方文档：赋值语句先求右侧，再绑定目标 ↗