递归
约 1490 字大约 5 分钟
2025-04-04
递归的核心是“把问题缩小成同形的子问题”。写好它只要两件事：明确终止条件、写出 f(n) 与 f(n-1) 的关系。这一节还会补两个工程现实：Python 不做尾递归优化，朴素递归常需要 functools.cache 做记忆化。
- 递归两件事：终止条件 + f(n) → f(n-1) 关系
- Python 默认深度限制 ~1000，可用 sys.setrecursionlimit 调
- Python 不做尾递归优化 —— 能写循环就别死磕递归
- 记忆化：@functools.cache 把 O(2ⁿ) 降到 O(n)
- 经典题型：阶乘、Fibonacci、汉诺塔、目录遍历
- 1写一个朴素 fib(n) 算第 35 项，掐表看它有多慢；再加 @functools.cache 看几乎瞬间出结果。
- 2把 factorial 改写成 while 循环版本，体会“能用循环就别用递归”在 Python 里的重要性。
- 3故意调一个深度 2000 的递归，看到 RecursionError；再 sys.setrecursionlimit(5000) 让它跑通。
- 4写一个遍历目录树的递归（os.scandir + 自调用），是递归在工程里的正经场景。
- 5用递归实现汉诺塔（递归经典题），并解释每一步“先把上面 n-1 块挪到中间柱”的子问题。
人理解函数，神理解递归。递归的精华是一递一归。所谓递，就是不断嵌套函数；所谓归，就是逐个将值返回。递而不归，就会越嵌套越深，直至突破内存极限而出错
递归函数的定义有两个方面：
- 不断调用自己本身（只满足这个条件的是死递归）
- 有明确的结束条件
例如，下面的这个函数就是一个死敌归：
python playground
def func():
print(1)
func()
func()程序并没有一直运行，持续打印 1，而是运行到一定深度（层次）后就停止了
这是因为 Python 为了保护计算机而设置了递归的深度限制。官方声明的限制是 1000 层，但实际测试往往在 998/997 层左右
我们也可以修改系统设置的迭代深度限制：
python playground
import sys
sys.setrecursionlimit(800)现在，让我们用递归写一个阶乘的函数：
python playground
import sys
sys.setrecursionlimit(800)
def factorial(n):
if n == 1:
return 1
else:
return factorial(n - 1) * n
print(factorial(5)) # 120递归的思路是：找到 f(n) 与 f(n - 1) 之间的关系，然后将这种关系作为返回值或者其他操作。通过设置起始位置或终止位置的函数值实现函数的结束条件
对于上个例子来说，factorial(n) 与 factorial(n - 1) 之间的关系是 factorial(n) = factorial(n - 1) * n。而当 n 为 1 时，factorial(1) = 1
把上面的例子拆开看就是下面这个样子：
| 函数层数 | n | 返回值 |
|---|---|---|
| factorial(5) | 5 | factorial(4) * 5 |
| 1 | 4 | factorial(3) * 4 * 5 |
| 2 | 3 | factorial(2) * 3 * 4 * 5 |
| 3 | 2 | factorial(1) * 2 * 3 * 4 * 5 |
| 4 | 1 | 1 * 2 * 3 * 4 * 5 |
有些问题使用递归解起来会有很奇妙的感觉，比如解决汉诺塔问题等。
但是因为层层嵌套，层层调用，递归非常占用内存，运行速度也相对缓慢。而且很多情况下，递归是可以转换成循环的，比如计算阶乘的函数可以写成：
python playground
def factor(n):
result = 1
while n > 0:
result *= n
n -= 1
return result
print(factor(5))Python 不做尾递归优化
许多语言（如 Scheme、Scala）会把“函数最后一行直接调用自己”的递归编译成循环，Python 故意不做这种优化。Guido 的理由是：保留完整调用栈对调试更友好。所以在 Python 里：
- 写递归别指望被自动优化掉；
- 涉及大数据/深度时，优先考虑改写为循环；
- 真要写很深的递归，要么手动维护一个栈，要么
sys.setrecursionlimit调大上限（仍然会更慢、更占内存）。
朴素递归的指数爆炸：用记忆化救场
著名的 Fibonacci 数列：fib(n) = fib(n-1) + fib(n-2)。最直观的递归写法是这样：
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)这段代码逻辑上完全正确，但 fib(35) 就开始变慢，fib(40) 几乎不可接受。原因是同一个子问题被反复求解 —— fib(30) 在树里出现了上百万次。
Python 3.9+ 在标准库提供了 functools.cache（更早版本叫 lru_cache），一行装饰器就能把朴素递归变成记忆化版本：
python playground
from functools import cache
@cache
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(50)) # 瞬间返回 12586269025记忆化通过空间换时间把指数复杂度压回到线性，是处理“重复子问题”类递归（动态规划、组合枚举）最直接的优化手段。
递归适合什么场景
递归在 Python 里更像一种思维工具而不是执行模型。它真正擅长的是这类问题：
- 树形/嵌套结构：目录树、JSON、HTML DOM、表达式树 —— 数据本身就是递归的。
- 分治：归并排序、快速排序、二分搜索的递归实现往往更直观。
- 回溯/组合枚举：八皇后、子集、排列、汉诺塔，递归 + 回退是最自然的表达方式。
线性顺序问题（求和、阶乘、累加），都更应该用循环 —— 既快又省内存。
- 写递归先想两件事：终止条件、f(n) 与子问题 f(n-1) 的关系。
- Python 不做尾递归优化，默认最大深度约 1000；线性问题尽量用循环。
- 重复子问题（典型 Fibonacci/DP）一律加 @functools.cache，O(2ⁿ) 立刻变 O(n)。
- 递归真正擅长的是“数据本身是树/嵌套”的场景：目录、JSON、表达式、分治、回溯。
- 调大 sys.setrecursionlimit 只是兜底，不是性能优化 —— 真要快还得改写算法。
版权所有
版权归属：Shuo Liu