Generating Permutations without Recursion: Common Non-Recursive Structure

[This page is auto-generated; please prefer to read the article’s PDF Form.]

Common Non-Recursive Structure

A generic approach to convert a recursive method into a non-recursive one is to simulate the recursive calls on our own stack within the method. This stack would contain the arguments and local variables for each recursive call. Such an approach was discussed in an earlier article titled Maintaining the Stack for Recursion [3].

But we will follow a diﬀerent approach below, which makes use of some speciﬁc observations about the generate() method. We will now inspect closely the execution ﬂow during the call generate(0).

First notice that for all s < N − 1, the generate() method is simply a loop: a sequence of iterations for each of i = 0,1,2,…,N − s − 1. Further, whenever a permutation is printed by generate(s = N − 1), each of the callers generate(0), generate(1), generate(2),…, generate(N − 2) are inside one of their iterations with certain i. The range to which this i can belong depends upon the respective s: 0 ≤ i ≤ N − s − 1.

To maintain this state i of (up to) N − 1 active invocations of the method, we will use an array I of N − 1 integers. I[s] will hold the value of i for invocation of generate(s). We don’t need to maintain i for s = N − 1.

Now notice that for any s < N − 1, an execution of generate(s) simply recurses to generate(s + 1) as the very ﬁrst step (after setting i = 0 in its ﬁrst iteration). The execution of generate(s + 1) would do the same thing and recurse to generate(s + 2). This goes on till execution of generate(N − 1) which prints the permutation. This suggests that, whenever an iteration has to make a recursive call, we can simply execute the equivalent of generate(N − 1): print the permutation. Though, this “execution” of generate(N − 1) must still “return” to its caller generate(N − 2).

To keep track of the currently executing generate() call (top of the call-stack), we will use an integer s which would correspond to the argument s of the call. Once generate(s) completes its last iteration (for i = N − s − 1), it should return to its caller. This is done by decrementing the tracking integer s.

These were some of the ideas on which the following non-recursive equivalent of generate() is based. In the while loop below, the beginning of any iteration can be seen as the point when an iteration of generate(s) resumes its operation after the recursive call generate(s + 1) has returned.

void generate_nonrecur()
{
  int I[N-1], s;

  for(s = 0; s < N-1; s++)
    I[s] = 0;

  /* "execute" generate(N-1) */
  print();

  /* "return" to the caller of generate(N-1) */
  s = N-2;

  while(s >= 0)
  {
    /* "resuming" after return from recursive call generate(s+1) */

    /* Cleanup Block */

    if(I[s] < N-s-1)
    {
      I[s]++;

      /* Setup Block */
      SWAP(s, x);

      /* "execute" generate(N-1) */
      print();

      /* "return" to the caller of generate(N-1) */
      s = N-2;
    }
    else
    {
      /* last iteration completed */
      I[s] = 0;

      /* "return" to the caller */
      s = s-1;
    }
  }
}

The above method will serve as a common skeleton for writing non-recursive variants of the recursive algorithms. For each algorithm, we only need to put the Setup Block and Cleanup Block (if any) in the place indicated in above method. The sections below will list the source code for the non-recursive variants thus created. Please refer article [2] for the description and recursive methods of the algorithms.