两个等价的JavaScript递归Heap排列生成器能否通过严谨代码转换相互推导？

没问题！咱们可以通过一步步的严谨代码转换，从实现1推导出实现2，清晰看到yield语句的位置迁移，以及base case如何“消失”。核心思路是把底层递归的输出逻辑逐步向上迁移，再简化冗余的判断逻辑。

先明确两个实现的核心差异 #

• 实现1：递归到最底层（n=1）时yield初始排列，上层递归通过yield*转发底层的所有输出，循环内先递归、再交换。
• 实现2：手动输出初始排列，递归函数无base case，循环内先递归、再交换，最后yield交换后的新排列。

步骤1：从实现1开始，分离初始排列的输出 #

实现1中，初始排列是由最底层的permutations(1)通过yield P输出的。我们可以把这个输出从递归函数中抽出来，改成主函数手动输出，同时修改底层递归的行为：

// 实现1原递归函数
function* permutations(n) {
  if (n == 1) yield P; // 这里输出初始排列
  else for (let i = 1; i <= n; i++) {
    yield* permutations(n - 1);
    if (i < n) swap(n, heap(n, i));
  }
}

// 第一步修改：把base case改成空返回，不再输出初始排列
function* permutations(n) {
  if (n == 1) return; // 现在permutations(1)是个空生成器
  else for (let i = 1; i <= n; i++) {
    yield* permutations(n - 1);
    if (i < n) swap(n, heap(n, i));
  }
}

// 主函数对应修改：手动输出初始排列
var count = 1;
console.log(count++, P.slice(1)); // 替代原来底层递归的初始输出
for (p of permutations(N)) console.log(count++, p.slice(1));

这一步的目的是为后续把yield迁移到交换操作后做准备——原来的输出依赖底层递归，现在我们要把输出逻辑放到交换完成后。

步骤2：把yield迁移到交换操作之后 #

在实现1中，每次交换后生成的新排列，是通过下一次递归调用的底层yield输出的。现在我们把输出逻辑直接放到交换操作之后，每次交换完成就yield当前的排列：

function* permutations(n) {
  if (n == 1) return;
  for (let i = 1; i <= n; i++) {
    yield* permutations(n - 1); // 现在这个调用不会输出任何内容
    if (i < n) {
      swap(n, heap(n, i));
      yield P; // 交换完成后直接输出新排列
    }
  }
}

现在，递归调用yield* permutations(n-1)只是触发交换逻辑的前置递归，不再负责输出；所有新排列的输出都由交换后的yield P完成。

步骤3：移除冗余的base case判断 #

现在看n=1的情况：当n=1时，循环i从1到1会执行一次：

1. yield* permutations(0)：调用permutations(0)时，循环i从1到0直接不执行，返回空生成器，所以这一行无任何输出；
2. i < 1不成立，跳过交换和yield。

也就是说，n=1时的if (n ==1) return和直接进入循环的行为完全一致——都是空操作，不会产生任何输出。因此我们可以安全地移除这个base case判断，得到：

function* permutations(n) {
  for (let i = 1; i <= n; i++) {
    yield* permutations(n - 1);
    if (i < n) {
      swap(n, heap(n, i));
      yield P;
    }
  }
}

这就是实现2的递归函数了！

反向转换（从实现2到实现1） #

如果想从实现2转回实现1，只需要反向执行上面的步骤：

1. 在递归函数中添加n=1时yield P的base case；
2. 移除循环内的yield P；
3. 主函数中移除手动输出的初始排列，恢复用for...of遍历生成器输出所有排列。

关键结论 #

两个实现完全可以通过严谨的代码转换相互推导：

• yield语句从递归最底层的base case位置，迁移到了上层循环的交换操作之后；
• base case并没有真的消失，而是被简化为循环的空执行逻辑，因为n=1时的循环行为和直接返回完全等价。

内容来源于stack exchange