一、一次给完，还是一个一个给

一百万个平方：列表占 8.1 MB，生成器占 200 字节，差 42244 倍。 列表把所有结果都算出来放好；生成器只记「算到哪了」，你说要下一个它才算。 这个对比要交代口径，不然会误导：那 8.1 MB 只是「装指针的数组」，每个整数本身还另占 28 字节。 真实占用三十多 MB，不是 8 MB。

而 200 字节是生成器对象自己的大小，里面一个结果都没有——它是空的，因为它只在需要时才算下一个。 所以「差四个数量级」这个结论成立，但别把 8.1 当成真实占用。 本课的原则是：数可以引用，口径必须跟着走。 那什么时候该用生成器？ 两种情况：数据量大到放不下，或者你只需要走一遍。 日志过滤、逐行读文件、流式处理网络数据， 都是这两个条件。

二、生成器只能走一遍

演示第二段：第一次 list(g) 得到 [0, 1, 2]，第二次得到 []。 走完就没了，不能回头。 要再走一遍，得重新造一个。 这是它省内存的代价：它不存结果，所以没有结果可以重放。

这个特性害过不少人：一个函数返回生成器，你拿它遍历了一遍做统计， 紧接着又想遍历一遍做输出——第二次是空的。 所以有条经验：生成器只在「最后一个消费者」那里用。 要多次使用，就先 list() 转成列表， 或者干脆返回列表。

三、用 yield 自己写生成器

函数体里一出现 yield，这个函数就变成生成器函数： 调用它不执行，只返回一个生成器；每次 next() 才往下跑到下一个 yield。 演示里 read_big(5) 先取三条得到 ['第 0 行', '第 1 行', '第 2 行']， 剩下的 list(it) 拿到 ['第 3 行', '第 4 行']。中间那条线就是「算到哪了」。 这就是「一行行读大文件」能不吃内存的原因——文件指针和当前行是状态，不是整个文件内容。

所以读一个 10 GB 的日志也只占几 MB，前提是你不写 readlines()。 那个函数会老老实实把 10 GB 读进内存。 for line in f 这种写法本身就是生成器行为，所以它天然省内存。 日常读文件用 for 循环就对了，不要手动 readlines。

四、递归：自己调自己

fact(5) 是 120，fact(20) 是 2432902008176640000，fib(10) 是 55，fib(20) 是 6765。 递归要两样东西：一个「什么时候停」的条件，一个「把问题缩小一点再调自己」。 fact(n) 那个 return 1 if n <= 1 else n * fact(n - 1) 就是这两样：n <= 1 是停的条件， n * fact(n - 1) 是把问题缩小。

缺一样就是无限递归。 Python 会在 1000 层左右把它掐掉，报 RecursionError。 递归写起来漂亮，是因为它的形状跟数学定义一模一样。 fib(n) = fib(n-1) + fib(n-2)，代码里就是这两个加法。没有比这更直白的写法了。

五、递归的代价

演示第五段数了调用次数：fib(10) 177 次，fib(20) 21,891 次，fib(25) 242,785 次。 n 只从 10 涨到 25，调用次数涨了一千三百多倍。 这叫指数级爆炸。 原因很朴素：fib(n-1) 里面算过的东西，fib(n-2) 里面又算一遍；再往下每一层都这么重复。

更要命的是：真正不同的子问题只有 25 个——fib(0) 到 fib(24)。可它把这几万个值算了几十万遍。 这个现象有个名字叫「重叠子问题」。看到它，就该想到缓存。

六、加缓存，回到线性

演示第六段加了一行 @functools.lru_cache(maxsize=None)：fib_memo(60) 得到1,548,008,755,920， 用时 0.0576 毫秒。 n 从 25 涨到 60，反而变快了。 因为它只算了 61 个不同的值，每个算一次。 演示里那行 CacheInfo(hits=58, misses=61, ...) 说的就是这件事：命中 58 次，真算 61 次。

对照那行：纯递归 fib(30) 用了 0.543 秒。同一台机器，一个半秒，一个零点零几毫秒。 这是动态规划的核心思想：不重复算同一个子问题。 能用递归写出来的问题，八成也能用一张表从下往上填——后者还不用担心栈溢出，也不用靠缓存。

但 lru_cache 不是万能的：它要求「同样的输入一定得到同样的输出」。 有副作用、依赖外部状态的函数不能缓存，否则你缓存的是过期数据。

七、递归太深会崩

Python 默认递归上限 1000 层。 演示里 deep(900) 正常返回，deep(100000) 崩了，报 maximum recursion depth exceeded。 每层调用都要占一块栈空间，而栈是有限的。 这不是 Python 小气，是所有语言都这样。 所以递归适合层数可控的问题：树的深度、目录层数、嵌套的 JSON。不适合「一共有一百万个」这种。

真要一百万层，两个办法：改成循环，或者用生成器自己维护一个栈。第二种在处理嵌套结构时更常见。 sys.setrecursionlimit 能调高， 但调太高会真的把栈撑爆，进程直接死，连报错都没有。 那比报错难查得多。 所以「递归改循环」在工程上常常是必须的，不是代码洁癖。能循环就别赌栈。

八、动手 Demo：生成器与递归

先量一下一百万个平方的内存占用，看列表和生成器差多少。 再看生成器走一遍就空、用 yield 自己写一个。 最后是递归：调用次数、加缓存、以及太深会崩。

import functools
import sys
import time

print('  ① 一次性给完，还是一个一个给')
print('  ' + '-' * 68)
lst = [i * i for i in range(1000000)]
gen = (i * i for i in range(1000000))
print('    列表 [i*i for i in range(1000000)]')
print('      实际占内存 %.1f MB' % (sys.getsizeof(lst) / 1048576.0))
print('    生成器 (i*i for i in range(1000000))')
print('      实际占内存 %d 字节' % sys.getsizeof(gen))
print('  列表把所有结果都算出来放好；生成器只记「算到哪了」，你说要下一个它才算。占用的差距是 %.0f 倍。'
      % (sys.getsizeof(lst) / float(sys.getsizeof(gen))))
print('  注意列表那个 MB 数只是「装指针的数组」，每个整数本身还另占 28 字节。')
print('  真实内存比上面这个数大得多——但「差好几个数量级」这个结论不变。')
print()
print('  ② 生成器只能走一遍')
print('  ' + '-' * 68)
g = (x for x in range(3))
print('    第一次 list(g) → %r' % list(g))
print('    第二次 list(g) → %r（空了）' % list(g))
print('  生成器是一次性的：走完就没了，不能回头。要再走一遍得重新造一个。这也是它省内存的代价。')
print()
print('  ③ 用 yield 自己写生成器')
print('  ' + '-' * 68)


def read_big(n):
    u"""假装从一个大文件里一行行读。"""
    for i in range(n):
        yield '第 %d 行' % i


it = read_big(5)
print('    前三条：%r' % [next(it) for _ in range(3)])
print('    剩下的：%r' % list(it))
print('  函数体里一出现 yield，这个函数就变成生成器函数：调用它不执行，只返回一个生成器；')
print('  每次 next() 才往下跑到下一个 yield。')
print('  这就是「一行行读大文件」能不吃内存的原因——文件指针和当前行是状态，不是整个文件内容。')
print()
print('  ④ 递归：自己调自己')
print('  ' + '-' * 68)


def fact(n):
    return 1 if n <= 1 else n * fact(n - 1)


def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)


print('    fact(5) = %d' % fact(5))
print('    fact(20) = %d' % fact(20))
print('    fib(10) = %d   fib(20) = %d' % (fib(10), fib(20)))
print('  递归要两样东西：一个「什么时候停」的条件（n<=1 返回 1），')
print('  一个「把问题缩小一点再调自己」（n * fact(n-1)）。缺一个就是无限递归。')
print()
print('  ⑤ 递归的代价：重复算了多少遍')
print('  ' + '-' * 68)
counter = [0]


def fib_count(n):
    counter[0] += 1
    return n if n < 2 else fib_count(n - 1) + fib_count(n - 2)


for n in (10, 20, 25):
    counter[0] = 0
    fib_count(n)
    print('    fib(%d) 一共调用了 %s 次' % (n, format(counter[0], ',')))
print('  n 只从 10 涨到 25，调用次数涨了一千多倍。')
print('  因为 fib(n-1) 和 fib(n-2) 里重复算了大量相同的子问题——这叫指数级爆炸。')
print()
print('  ⑥ 加个缓存，立刻回到线性')
print('  ' + '-' * 68)


@functools.lru_cache(maxsize=None)
def fib_memo(n):
    return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)


t0 = time.perf_counter()
v = fib_memo(60)
t1 = time.perf_counter() - t0
print('    fib_memo(60) = %s，用时 %.4f 毫秒' % (format(v, ','), t1 * 1000))
print('    缓存命中情况 %r' % (fib_memo.cache_info(),))
t0 = time.perf_counter()
v2 = fib(30)
t2 = time.perf_counter() - t0
print('    对照：纯递归 fib(30) = %s，用了 %.3f 秒' % (format(v2, ','), t2))
print('  同一个递归，加一行 lru_cache，从「n=30 就要 %.2f 秒」变成「n=60 一瞬间」。' % t2)
print('  这是动态规划的核心思想：不重复算同一个子问题。')
print('  能用递归写出来的问题，八成也能用一张表从下往上填——后者还不用担心栈溢出。')
print()
print('  ⑦ 递归太深会崩')
print('  ' + '-' * 68)
print('    Python 默认递归上限 %d 层' % sys.getrecursionlimit())


def deep(n):
    return 0 if n == 0 else 1 + deep(n - 1)


try:
    deep(900)
    print('    deep(900) 正常返回')
except RecursionError as e:
    print('    deep(900) 崩了：%s' % e)
try:
    deep(100000)
except RecursionError as e:
    print('    deep(100000) 崩了：%s' % e)
print('  每层调用都要占一块栈空间，栈是有限的。')
print('  所以「递归」适合层数可控的问题（树的深度、目录层数），不适合「一共有一百万个」这种。')
print('  真要一百万层，两个办法：改成循环，或者用生成器自己维护一个栈。')
print('  sys.setrecursionlimit 能调高，但调太高会真的把栈撑爆，进程直接死，连报错都没有。')

实跑输出：

--------------------------------------------------------------------
生成器与递归
--------------------------------------------------------------------

  ① 一次性给完，还是一个一个给
  --------------------------------------------------------------------
    列表 [i*i for i in range(1000000)]
      实际占内存 8.1 MB
    生成器 (i*i for i in range(1000000))
      实际占内存 200 字节
  列表把所有结果都算出来放好；生成器只记「算到哪了」，你说要下一个它才算。占用的差距是 42244 倍。
  注意列表那个 MB 数只是「装指针的数组」，每个整数本身还另占 28 字节。
  真实内存比上面这个数大得多——但「差好几个数量级」这个结论不变。

  ② 生成器只能走一遍
  --------------------------------------------------------------------
    第一次 list(g) → [0, 1, 2]
    第二次 list(g) → []（空了）
  生成器是一次性的：走完就没了，不能回头。要再走一遍得重新造一个。这也是它省内存的代价。

  ③ 用 yield 自己写生成器
  --------------------------------------------------------------------
    前三条：['第 0 行', '第 1 行', '第 2 行']
    剩下的：['第 3 行', '第 4 行']
  函数体里一出现 yield，这个函数就变成生成器函数：调用它不执行，只返回一个生成器；
  每次 next() 才往下跑到下一个 yield。
  这就是「一行行读大文件」能不吃内存的原因——文件指针和当前行是状态，不是整个文件内容。

  ④ 递归：自己调自己
  --------------------------------------------------------------------
    fact(5) = 120
    fact(20) = 2432902008176640000
    fib(10) = 55   fib(20) = 6765
  递归要两样东西：一个「什么时候停」的条件（n<=1 返回 1），
  一个「把问题缩小一点再调自己」（n * fact(n-1)）。缺一个就是无限递归。

  ⑤ 递归的代价：重复算了多少遍
  --------------------------------------------------------------------
    fib(10) 一共调用了 177 次
    fib(20) 一共调用了 21,891 次
    fib(25) 一共调用了 242,785 次
  n 只从 10 涨到 25，调用次数涨了一千多倍。
  因为 fib(n-1) 和 fib(n-2) 里重复算了大量相同的子问题——这叫指数级爆炸。

  ⑥ 加个缓存，立刻回到线性
  --------------------------------------------------------------------
    fib_memo(60) = 1,548,008,755,920，用时 0.0576 毫秒
    缓存命中情况 CacheInfo(hits=58, misses=61, maxsize=None, currsize=61)
    对照：纯递归 fib(30) = 832,040，用了 0.543 秒
  同一个递归，加一行 lru_cache，从「n=30 就要 0.54 秒」变成「n=60 一瞬间」。
  这是动态规划的核心思想：不重复算同一个子问题。
  能用递归写出来的问题，八成也能用一张表从下往上填——后者还不用担心栈溢出。

  ⑦ 递归太深会崩
  --------------------------------------------------------------------
    Python 默认递归上限 1000 层
    deep(900) 正常返回
    deep(100000) 崩了：maximum recursion depth exceeded
  每层调用都要占一块栈空间，栈是有限的。
  所以「递归」适合层数可控的问题（树的深度、目录层数），不适合「一共有一百万个」这种。
  真要一百万层，两个办法：改成循环，或者用生成器自己维护一个栈。
  sys.setrecursionlimit 能调高，但调太高会真的把栈撑爆，进程直接死，连报错都没有。

第一段那个 8.1 MB 和 200 字节是同一个东西的两种形态。 注意这里量的只是「装指针的数组」，整数本身另算——所以真实差距比 42244 倍还大。 第二段那个 [] 是很多人第一次踩的坑：生成器遍历完就空了，第二次拿到的是空列表，而且不报错。 第五段那三个数值得记住量级：25 就已经 24 万次了。再往上加 5，就是几百万次。 第六段那个 CacheInfo 是本篇最实在的一行：命中 58 次、真算 61 次，所以它才是线性的。 第七段 900 能过、100000 崩，中间那条线就是 1000。想看它崩在哪，把 900 改成 990、995、999 试一下。

30 秒实验

1. 把演示第一段的一百万改成五百万，看列表那个 MB 数涨到多少、生成器那个字节数变不变。
2. 把演示第三段的 read_big(5) 改成 read_big(1000000)，但只用前三条——看它是不是一瞬间就返回。
3. 把演示第六段的 @functools.lru_cache(maxsize=None) 删掉，跑 fib_memo(60)， 看它是不是直接卡住（等十秒就掐掉）。

常见误区

1. 「生成器比列表快。」它省内存，不一定更快。 有的场景生成器还更慢，因为每次取值都要多一层开销。
2. 「递归写得简洁，就用递归。」层数一多就崩，重复子问题还会指数爆炸。 简洁是给人的，崩溃是给用户的。
3. 「加个 lru_cache 就万能了。」它只对「同样输入得到同样输出」的函数有效。 有副作用、读外部状态的函数，缓存下来的是错的数据。

附录 A 结束。下一篇进附录 B：让一块 MicroPython 板子发消息、开灯。

• ☐ （本篇完，下一篇 B.1 从 MicroPython 发消息到开关灯）

相关笔记

• 列表生成式与装饰器
• 自定义函数与再谈列表
• 编程原理 · 索引
• 🐍 超图解 Python 程序设计入门 · 索引