UCB CS61A树递归生成器partition_gen的行为机制与核心疑问

我当初学CS61A的时候，被递归生成器绕得晕头转向，尤其是这个partition_gen的例子——咱们一步步拆解你的疑问，把它彻底搞明白。

先理清partition_gen的核心逻辑（三个独立分支！） #

首先要注意：函数里的三个if是并列独立的，不是互斥的if-elif-else！这是理解所有行为的关键：

• 分支1：如果n == m，直接 yield 当前数的字符串（比如partition_gen(2,2)会先yield "2"）
• 分支2：如果n > m，递归生成n-m的所有分区（最大数不超过m），每个结果后面加上 + m再yield（这对应“包含至少一个m的分区”）
• 分支3：如果m > 1，直接转发partition_gen(n, m-1)的所有结果（这对应“完全不包含m的分区”）

每个生成器都是一个带状态的迭代器：每次调用next()时，从上次暂停的位置继续执行，直到遇到下一个yield或者函数结束（触发StopIteration）。

拆解三次next(A)的执行流程 #

咱们从A = partition_gen(6,4)开始，一步步追踪每一次next()的路径：

第一次next(A) → 返回"2 + 4" #

1. 启动partition_gen(6,4)：
   • 分支1：6≠4，跳过；
   • 分支2：6-4=2>0，进入循环for p in partition_gen(2,4)，需要先迭代partition_gen(2,4)的结果；
2. 进入partition_gen(2,4)：
   • 分支1：2≠4，跳过；
   • 分支2：2-4=-2<0，跳过；
   • 分支3：4>1，yield from partition_gen(2,3)，转发partition_gen(2,3)的结果；
3. 进入partition_gen(2,3)：
   • 分支1：2≠3，跳过；
   • 分支2：2-3=-1<0，跳过；
   • 分支3：3>1，yield from partition_gen(2,2)，转发partition_gen(2,2)的结果；
4. 进入partition_gen(2,2)：
   • 分支1：2==2，yield "2"——这个结果一路向上转发，最终回到partition_gen(6,4)的循环里，拼接成"2 + 4"，这就是第一次next()的返回值。

此时，partition_gen(2,2)的执行暂停在分支1之后，还没处理后面的分支！

第二次next(A) → 返回"1 + 1 + 4" #

1. 继续执行上次暂停的partition_gen(2,2)：
   • 分支2：2-2=0，不满足，跳过；
   • 分支3：2>1，yield from partition_gen(2,1)，转发partition_gen(2,1)的结果；
2. 进入partition_gen(2,1)：
   • 分支1：2≠1，跳过；
   • 分支2：2-1=1>0，进入循环for p in partition_gen(1,1)；
3. 进入partition_gen(1,1)：
   • 分支1：1==1，yield "1"——拼接成"1 + 1"，一路向上转发到partition_gen(6,4)，变成"1 + 1 + 4"，这就是第二次next()的返回值。

这里你之前的误解是以为会“重新调用partition_gen(2,2)”，但实际上是同一个partition_gen(2,2)生成器在继续执行剩下的代码，它还没耗尽呢！

第三次next(A) → 返回"3 + 3" #

1. 当partition_gen(2,4)的所有结果（"2"和"1+1"）都处理完后，partition_gen(6,4)的分支2循环结束，继续执行分支3：
   • 分支3：4>1，yield from partition_gen(6,3)；
2. 进入partition_gen(6,3)：
   • 分支1：6≠3，跳过；
   • 分支2：6-3=3>0，进入循环for p in partition_gen(3,3)；
3. 进入partition_gen(3,3)：
   • 分支1：3==3，yield "3"——拼接成"3 + 3"，这就是第三次next()的返回值。

解答你的两个关键疑问 #

1. 为什么第三次调用partition_gen(2,2)没有触发StopIteration？ #

其实根本没有“第三次调用partition_gen(2,2)”！第一次调用的partition_gen(2,2)在yield "2"之后，还在继续执行分支3的逻辑，直到partition_gen(2,1)的所有结果都处理完，这个生成器才会耗尽（触发StopIteration）。生成器的生命周期是从创建到所有代码执行完毕，不是每次yield就重新创建。

2. 怎么思考树递归生成器？ #

别把它想得太复杂，你可以沿用普通递归函数的“归纳假设”思路，只需要把“返回结果”换成“生成所有结果”：

• 假设partition_gen(k, t)能正确生成k的所有分区（最大数不超过t）；
• 那么partition_gen(n, m)的结果就是三部分的组合：
  1. 单独的n（当n==m时）；
  2. 所有包含m的分区：partition_gen(n-m, m)的每个结果加上 + m；
  3. 所有不包含m的分区：直接用yield from转发partition_gen(n, m-1)的结果；

唯一需要额外注意的是：生成器是懒加载的，它不会一次性生成所有结果，而是每次next()才生成下一个。你不需要手动跟踪每个递归调用的状态，只需要相信子生成器能正确生成它的结果，父生成器负责把这些结果按逻辑组合或转发即可。

备注：内容来源于stack exchange，提问作者William Wang