跳转到内容
← 返回核心概念
计算机科学基础计算机科学 · 算法 · 程序设计约 15 分钟阅读

递归

Recursion

字典里如果有这样一条词条："递归，见：递归"，读者会感到困惑和被戏弄。 然而计算机科学里，这种用自身定义自身的方式，是一种精密的、有时是唯一自然的表达方式。递归是现代计算机语言的核心能力之一，也是理解许多算法和数据结构的钥匙。

递归分治调用栈归纳法不动点

字典里如果有这样一条词条："递归，见：递归"，读者会感到困惑和被戏弄。

然而计算机科学里，这种用自身定义自身的方式，是一种精密的、有时是唯一自然的表达方式。递归是现代计算机语言的核心能力之一，也是理解许多算法和数据结构的钥匙。

这份"核心能力"并非自来就有。1960 年，John McCarthy 在那篇定义 LISP 的论文（《符号表达式的递归函数及其机器计算》）中，把递归提升为编程语言的一等控制结构——同时代的 FORTRAN 甚至没有标准的递归调用机制。随后 ALGOL 60 引入了递归过程，递归才逐渐成为通用语言的标配。

破除误解：递归不等于循环

初学者常把递归和 for 循环混为一谈。两者确实都能重复执行某件事，但结构完全不同。

循环是迭代：维护一个状态变量，每轮更新它，直到条件满足停止。

递归是自我引用：一个函数调用自己，直到抵达某个不再需要递归的"基础情况"（base case），然后返回值逐层向上传递。

更准确地说，递归是一种思维方式：把一个大问题分解为同样形状但规模更小的子问题，直到子问题小到可以直接回答。这不仅仅是编程技巧，而是数学归纳法在计算上的对应物。

现场：汉诺塔与目录遍历

汉诺塔问题：三根柱子，N 个大小不同的圆盘叠在第一根柱子上（大的在下），要把所有圆盘移到第三根柱子，每次只能移一个，且大盘不能压小盘。

非递归地想这个问题令人头疼。递归的思路清晰到几乎是废话：

  1. 先把上面的 N-1 个盘子从柱子 A 移到柱子 B（递归）
  2. 把最大的盘子从 A 移到 C
  3. 再把 N-1 个盘子从 B 移到 C（递归）
python
def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    hanoi(n - 1, source, auxiliary, target)
    print(f"Move disk {n} from {source} to {target}")
    hanoi(n - 1, auxiliary, target, source)
```

七行代码，解决了一个需要 2n−12^n - 1 步的问题。

文件系统遍历是现实中无处不在的递归：一个目录可以包含文件和子目录，子目录又可以包含文件和子目录……这种递归定义的数据结构（树）天然地用递归来处理。

递归必须有终止条件

递归陷阱：如果一个函数无限调用自己而永不触底，程序会耗尽调用栈（stack overflow）崩溃。

合法的递归必须满足两个条件： 1. 基础情况：存在至少一个不需要递归的情况直接返回结果 2. 收缩保证：每次递归调用，问题规模必须严格缩小，朝向基础情况

著名的错误递归示例：

python
def fibonacci_wrong(n):
    return fibonacci_wrong(n - 1) + fibonacci_wrong(n - 2)
    # 没有基础情况——永远不会停止
```

正确写法：

python
def fibonacci(n):
    if n <= 1:          # 基础情况
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)
```

调用栈：递归在机器里的样子

每次函数调用，程序在内存中压入一个"栈帧"（stack frame），记录当前函数的参数、局部变量、返回地址。函数返回时弹出。

递归就是把许多栈帧叠起来：

fibonacci(5)
  fibonacci(4)
    fibonacci(3)
      fibonacci(2)
        fibonacci(1) → 1
        fibonacci(0) → 0
      → 1
    → 2
  → 3
→ 5
```

栈帧并不免费：主流平台的线程栈默认只有数 MB 量级（Linux 下常见 8 MB，Windows 常见 1 MB），每个帧占用几十到几百字节，深度十万的递归就能把它耗尽——这就是"栈溢出"（stack overflow）的物理来源，也是那个著名程序员问答网站名字的由来。

还要区分两种低效：深度决定空间（栈帧的最大叠加数），调用树的总节点数决定时间。朴素 fibonacci 的深度只有 $O(n)$——栈不是问题；问题在于调用树有 O(2n)O(2^n) 个节点，同一批子问题被反复展开重算。

这意味着递归的空间代价是调用深度的函数——对于深度 $n$ 的递归，需要 $O(n)$ 的栈空间。这正是朴素 Fibonacci 递归虽然代码优雅，却极度低效的原因：它重复计算了大量子问题，时间复杂度是指数级 O(2n)O(2^n)。

尾递归与编译器优化

一种特殊的递归形态——尾递归（tail recursion）——递归调用是函数最后一步，返回值直接就是递归调用的结果，没有后续操作：

python
def factorial_tail(n, accumulator=1):
    if n == 0:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)
    # 这里的递归调用是最后一步
```

为什么尾调用可以安全地复用栈帧？因为递归调用之后不再有任何待办的计算：当前帧里的局部变量与返回地址从此再无用处，新调用可以直接覆盖旧帧，"返回"退化为一次跳转。反过来，只要调用之后还有事要做——比如 return fibonacci(n - 1) + fibonacci(n - 2) 里的那次加法——旧帧就必须保留，优化无从谈起。资源管理语义也会挡路：C++ 的析构函数、Java 的 finally 块都要在返回前执行，这些"尾巴上的活儿"让看似尾位置的调用实际不是尾调用。

支持尾递归优化（Tail Call Optimization, TCO）的语言/编译器，可以把尾递归转化为迭代，消除栈的累积——等于用 $O(1)$ 空间完成递归。Scheme 语言规范强制要求 TCO，递归因此成为 Scheme 里替代循环的正统写法；Haskell、Erlang 也有支持。Python 和 Java 默认不做 TCO，这是一个有意的设计决策（保留完整调用栈便于调试）。Python 的拒绝最直白：Guido van Rossum 在 2009 年公开解释过，消除栈帧会让错误回溯（traceback）丢失关键信息，Python 选择可读的错误报告，而不是 $O(1)$ 空间的递归。ECMAScript 2015 则提供了一个耐人寻味的对照：标准写入了"proper tail calls"，但多年过去只有 Safari 的 JavaScriptCore 真正实现——其余引擎担心隐形的栈行为变化破坏调试与栈深度检查，宁可让标准条文悬空。

递归与归纳：数学上的对应

数学归纳法证明"命题 $P(n)$ 对所有正整数 $n$ 成立"：

  1. 证明 $P(1)$ 成立（基础情况）
  2. 证明若 $P(k)$ 成立，则 $P(k+1)$ 成立（递推）

这与递归函数的结构完全同构：基础情况 + 从小到大的归约。理解了这一点，就理解了为什么递归证明正确性往往比分析迭代程序更容易——递归程序的结构和证明的结构完全一一对应。

把对应再说深一层：写一个递归函数，就是在写一个归纳证明。定义 hanoi 时假设"N-1 个盘子的版本已经能正确工作"，这正是归纳假设；基础情况是归纳起点；"问题规模严格缩小"保证归纳良基。对树结构的递归对应结构归纳法：证明"对叶子成立"，且"若对左右子树成立则对整棵树成立"。

终止性也可以形式化：给每次递归调用找一个度量（自然数，或更一般的良序集元素），证明它严格递减。良序集没有无限下降链，递归必然终止。反过来，找不到这样的度量往往不是技巧不够——Ackermann 函数（见下文）的终止性就无法用单参数递减证明，必须对参数对 $(m, n)$ 按字典序递减，这正是它超出原始递归（见下文）的地方在证明论上的倒影。

互递归与 Y 组合子

互递归（Mutual Recursion）：两个函数互相调用对方，每次调用都使问题规模缩小：

python
def is_even(n):
    if n == 0: return True
    return is_odd(n - 1)

def is_odd(n): if n == 0: return False return is_even(n - 1) ```

这在处理相互依赖的语法规则（如"表达式"定义中包含"语句"，"语句"又包含"表达式"）时很自然。

更深的问题：如果语言不支持给函数命名，还能实现递归吗？

Y 组合子（Haskell Curry，1940 年代）的答案是肯定的。Y 组合子是一个高阶函数，接受一个"几乎是递归函数"的函数（但不直接调用自身），返回它的不动点——一个真正递归的版本：

Y=λf.(λx.f (x x)) (λx.f (x x))Y = \lambda f. (\lambda x. f\ (x\ x))\ (\lambda x. f\ (x\ x))

验证：Y f=(λx.f (x x)) (λx.f (x x))=f ((λx.f (x x)) (λx.f (x x)))=f (Y f)Y\ f = (\lambda x. f\ (x\ x))\ (\lambda x. f\ (x\ x)) = f\ ((\lambda x. f\ (x\ x))\ (\lambda x. f\ (x\ x))) = f\ (Y\ f)

即 Y f=f (Y f)Y\ f = f\ (Y\ f)——Y fY\ f 是 $f$ 的不动点。

这个数学技巧证明了：递归不是语言的"特性"，而是高阶函数能力的逻辑推论。任何支持高阶函数的语言（即使不支持命名递归），都可以通过 Y 组合子实现递归。这是 λ 演算完备性的核心论据。

原始递归与全递归

数学逻辑中，递归有两种严格的层级：

原始递归（Primitive Recursive）：通过有限次基本操作和"递归方案"（对自然数归纳定义）得到的函数，包括加法、乘法、阶乘等。所有原始递归函数都是全函数（对所有输入终止）。

全递归（General Recursive / μ递归）：在原始递归基础上加入"最小化"操作（找使某条件成立的最小值），表达力等价于图灵机。但全递归函数可能对某些输入不终止（停机问题的根源）。

Ackermann 函数（1928）是一个全递归但非原始递归的函数，其增长速度超过任何原始递归函数：

A(0,n)=n+1A(0, n) = n + 1 A(m,0)=A(m−1,1)(m>0)A(m, 0) = A(m-1, 1) \quad (m > 0) A(m,n)=A(m−1,A(m,n−1))(m,n>0)A(m, n) = A(m-1, A(m, n-1)) \quad (m, n > 0)

$A(4, 2)$ 的值是 265536−32^{65536} - 3，一个有 19729 位的整数——远远超过可观测宇宙中的原子数量（约 108010^{80}）。Ackermann 函数证明了：有些函数在直觉上"可以计算"，却完全逃出了"循环+简单递归"的表达能力范围。

代价与争议：优雅还是低效？

递归的争议主要在工程实践层面：

  • 性能：函数调用有开销（压栈、弹栈）。对于简单的迭代问题，递归版本比迭代慢，有时慢很多。
  • 栈溢出风险：Python 默认递归深度限制在 1000。处理大型数据集时，朴素递归可能因栈溢出崩溃。
  • 可读性的两面：对于树、图等递归结构，递归代码优雅清晰；对于本质上是循环的问题，强行用递归反而令人困惑。

实际工程中常用的折中方案：记忆化递归（memoization）——缓存已计算过的子问题结果，把指数复杂度降为线性，同时保留递归的可读性。这也是动态规划的本质之一。

跨域连接

  • 证明：递归与数学归纳法结构同构——基础情况对应起点，收缩保证对应归纳步。把这层对应说透就得到终止性检查的原理：证明一个递归函数会停，等价于给出一个映到良序集上的严格递减度量。反过来，找不到这样的度量往往不是技巧不够，而是该函数在某些输入上确实不停机。
  • 哥德尔不完备定理：Y 组合子构造不动点用的对角化手法，与哥德尔把「本命题不可证」编码进算术是同一招。这条线索把三件事串起来：在逻辑里它产出不可判定命题，在计算里它产出无需命名的递归，在可计算性里它产出停机问题的反证。自我指涉因此不是花招，而是形式系统一旦足够强就无法回避的结构。
  • 句法学：有限的规则加上可嵌入的结构，就能生成无限多的句子——这是「离散无限性」主张的核心，也使它成为可证伪的：只要确证存在一种完全没有句法嵌入的自然语言，把递归当作语言能力普遍特征的主张就受到直接挑战。相关争论至今未定，但值得注意的是它的形式与终止性问题一样，落在能否找到反例上。
  • 演化发育生物学：血管、气管、叶脉这类分支结构由局部重复的规则生成，基因组不必编码每一根分支的位置，只需编码分支规则——这与用有限代码描述无限结构是同一种压缩。推论可观察：这类结构的变异通常表现为规则参数改变，从而整片分支模式一起变形，而不是某一根分支单独消失。
  • 动态规划：朴素递归的指数代价来自重复求解同一批子问题，记忆化把复杂度降到子问题个数乘以每个的合并代价。这正好点明「最优子结构加重叠子问题」这两个条件的实际含义：一个问题能被高效求解，取决于它的子问题空间是否只有多项式大小。子问题空间一旦爆炸，缓存也救不回来。

参考文献

  • Abelson, H. & Sussman, G. Structure and Interpretation of Computer Programs. MIT Press, 1996. （第1章深入讲述递归与过程）
  • McCarthy, J. Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. CACM 3(4) (1960): 184–195. （LISP 的定义性论文，递归作为一等控制结构）
  • Kleene, S. C. General Recursive Functions of Natural Numbers. Mathematische Annalen 112, 1936.（原始递归与全递归的奠基论文）

延伸阅读

  • Hofstadter, D. Gödel, Escher, Bach: An Eternal Golden Braid. Basic Books, 1979. （递归、自我指涉与意识的跨学科经典）
  • Sedgewick, R. & Wayne, K. Algorithms. 4th ed. Addison-Wesley, 2011. （含大量递归算法的标准教材）

正文中引用本条 · 2 · 其中 1 条来自其他领域

数学证明的艺术