I have two JavaScript generator functions for permutations. They both provide Heap's enumeration.

Question: I would like to know whether one implementation can be derived from the other by some rigorous code transformation. In particular, I would like to see, how the yield statement might "travel" from its earlier position to its later one and how the base case could (apparently) "vanish".

The source code is re-edited to be runnable as self-contained code snippets, even though in the literature it is common to see algorithms with "globals".

The question is not about the popular recursive vs. iterative issue. Let us stick to recursive.

The code was inspired by Robert Sedgewick's paper, Permutation Generation Methods (1977), where on page 140 he introduces the following basic recursive algorithm:

To generate all permutations of P[1], ..., P[N], we repeat N times the step: "first generate all permutations of P[1], ..., P[N-1], then exchange P[N] with one of the elements P[1], ..., P[N-1]."

However, that does not truely give Heap's algorithm since during the last iteration of the repeat loop, there is a superfluous exchange. If that is removed, we end up with implementations which seem to be equivalent to the recursive solution given in Wikipedia. In any case, when called for N = 4 it reproduces Heap's enumeration as given in Sedgewick's paper. Please do not dwell on edge cases or negative N. Also, I do not consider it an important feature that implementation 1 produces the original permutation just so, whereas it has to be manually provided for in the other implementation.

Implementation 1:

function permute(N) {
  function swap(x, y) { [ P[x], P[y] ] = [ P[y], P[x] ] }
  function heap(n, i) { return (n % 2) || i }

  var P = []; for (let i = 1; i <= N; i++) P[i] = i;
  var count = 1;
    
  for (p of permutations(N)) console.log(count++, ":", p.slice(1));

  function* permutations(n) {
    // Recursion base case
    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));
    }
  }
}

permute(4);

Implementation 2:

function permute(N) {
  function swap(x, y) { [ P[x], P[y] ] = [ P[y], P[x] ] }
  function heap(n, i) { return (n % 2) || i }

  var P = []; for (let i = 1; i <= N; i++) P[i] = i;
  var count = 1;
  console.log(count++, ":", P.slice(1));
    
  for (p of permutations(N)) console.log(count++, ":", p.slice(1));

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

Note that I simply ignore the element at index 0 of JavaScript arrays by initialising array P suitably and by using the slice() method to log only the subarray starting at index 1. This is done to remain compatible with frequently found pseudocode in Sedgewick and elsewhere.

For clarification: what do I mean by code transformation? Sedgewick himself gives examples. First he starts off with his Algorithm 1 on page 140, which is recursive. He first gives a (rather loose) transformation into a first nonrecursive form on page 142. This one he then transforms three times into some final form which, when given directly, would be hard to consider equivalent to the initial one. But take this as a model only; I am not asking about the recursive vs. iterative issue.