Tower of Hanoi: Transforming the Recursion: Non-Recursive Equivalent

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

Non-Recursive Equivalent

We will use the parameter-less method recur2() to write a non-recursive equivalent of the recursive algorithm. As said earlier, we will maintain our own stack to simulate the recursive calls.

Method recur2() has no arguments and no local state to be stored on the stack for each call. We only need to store the equivalent of instruction-pointer (as happens for the call-stack) to indicate where to resume execution after a recursive call returns. There are two recursive calls in this method and hence only two possible resume-points (the very next statement to execute after a call returns). We will identify these resume-points by integers 1 and 2. A special value 0 of resume-point will be used to indicate a fresh call (not an actual resume); this will make our implementation simpler.

So, our stack-frame for each call is a very small one, consisting of only the resume-point. As recursive calls are made and return, these frames are pushed-on and popped-oﬀ the stack.

The global 4-tuple g can now be made local in the method; we will unwrap its members such that they also serve as the parameters of this method.

#define SWAP(x, y) { int t; t = x; x = y; y = t; }

void nonrecur(int n, int s, int d, int a)
{
  /* each frame of this stack actually requires only 2 bits, for
     storing one of the resume-points: 0, 1, 2 */
  char stack[n];
  int top;

  stack[0] = 0;
  top = 0;

  while(top >= 0)
  {
    /* execute a code-block of recur2() according to the current
       resume-point */
    switch(stack[top])
    {
      case 0:
        if(n == 1)
        {
          MOVE(s, d);
          /* return from this call */
          top--;
          continue;
        }

        n = n - 1;
        SWAP(d, a);
        /* make the first recursive call */
        stack[top] = 1;
        stack[++top] = 0;
        break;

      case 1:
        SWAP(d, a);
        MOVE(s, d);
        SWAP(s, a);
        /* make the second recursive call */
        stack[top] = 2;
        stack[++top] = 0;
        break;

      case 2:
        SWAP(s, a);
        n = n + 1;
        /* return from this call */
        top--;
        break;
    }
  }
}