递归生成器的运行机制是怎样的？以Python全排列实现代码为例

递归生成器本质是递归调用栈 + 每层独立的生成器状态机的组合，没有特殊的底层魔法，只是把普通递归的「一次性计算所有结果返回」逻辑，改成了「每层生成器按需产出结果，暂停保留状态等待下一次触发」的逻辑。

我们直接以你写的排列函数为例，结合你的调试日志拆解运行过程：
你使用的核心代码如下：

def _permutate(elems):
    if len(elems) <= 1:
        print(elems) # NEW
        yield elems
    else:
        for i in range(len(elems)):
            for perm in _permutate(elems[:i] + elems[i+1:]):
                print("NEW", [elems[i]], perm)  # NEW
                yield [elems[i]] + perm

测试代码为：

gen = _permutate([1,2,3,4,5])
print('NEXT', next(gen))

第一次调用next的完整流程 #

1. 执行gen = _permutate([1,2,3,4,5])时，函数没有执行任何实际逻辑，仅返回了一个顶层生成器对象，这是生成器的基础特性。
2. 第一次调用next(gen)时，顶层生成器正式启动执行：
   • 入参长度为5>1，进入外层for循环，i取第一个值0
   • 遇到for perm in _permutate(elems[:0] + elems[1:])语句，调用_permutate([2,3,4,5])得到第二层生成器对象，迭代触发它执行
   • 第二层生成器执行：入参长度4>1，外层for循环i取0，调用_permutate([3,4,5])得到第三层生成器，触发执行
   • 第三层生成器：入参长度3>1，i取0，调用_permutate([4,5])得到第四层生成器，触发执行
   • 第四层生成器：入参长度2>1，i取0，调用_permutate([5])得到第五层生成器，触发执行
   • 第五层生成器：入参长度1<=1，执行print输出[5]，随后yield返回[5]，第五层生成器进入暂停状态，把结果返回给第四层的perm变量
3. 第四层拿到perm=[5]，执行print输出NEW [4] [5]，随后yield返回[4,5]，进入暂停状态，把结果返回给第三层的perm变量
4. 第三层拿到perm=[4,5]，执行print输出NEW [3] [4, 5]，随后yield返回[3,4,5]，进入暂停状态，把结果返回给第二层的perm变量
5. 第二层拿到perm=[3,4,5]，执行print输出NEW [2] [3, 4, 5]，随后yield返回[2,3,4,5]，进入暂停状态，把结果返回给第一层的perm变量
6. 第一层拿到perm=[2,3,4,5]，执行print输出NEW [1] [2, 3, 4, 5]，随后yield返回[1,2,3,4,5]，进入暂停状态，这个值就是第一次next的返回值，和你日志里的第一个NEXT输出完全对应。

第二次调用next的核心差异 #

普通递归执行到这一步已经计算完所有结果、清空了整个调用栈，但递归生成器的每一层都还处于暂停状态，各自保留了当前的循环变量值、执行位置等状态：

1. 触发顶层生成器继续执行，顶层当前还在i=0的循环中，刚完成一次yield，回到内层for循环要求取下一个perm值，因此触发第四层生成器继续执行
2. 第四层生成器刚才在i=0的循环中完成了一次yield，现在继续执行i=0的内层for循环，要求取下一个perm，但第五层生成器已经迭代完毕（长度为1的生成器仅能产出1个值），因此第四层的循环变量i自增到1
3. 第四层i=1，调用_permutate([4])（当前层入参为[4,5]，i=1时截取子数组为elems[:1] + elems[2:] = [4]），得到新的第五层生成器，触发执行
4. 第五层生成器执行print输出[4]，yield返回[4]，返回给第四层的perm变量
5. 后续流程和第一次调用的后半段完全一致，逐层向上返回结果，最终第一层yield返回[1,2,3,5,4]，就是你日志里的第二个NEXT输出。

递归生成器的核心特性 #

• 每个递归调用返回的生成器都是完全独立的，各自保留自己的执行状态（循环变量、当前执行位置、局部变量值）
• 只有上层生成器迭代需要下一个值时，下层生成器才会继续执行，不会提前计算所有结果，内存占用极低
• 调用栈的压入弹出逻辑和普通递归一致，但普通递归是一次性走到基准条件再逐层返回所有结果，递归生成器是走到基准条件产出一个值就逐层返回暂停，下一次触发时从上次暂停的位置继续执行，直到当前层所有值都产出完毕，才会回到上一层让循环变量自增，继续生成下一组结果。

内容的提问来源于stack exchange，提问作者Domanowska