The non-recursive method hanoi follows. It has been created by following the rules of the main text. Please note, that we use arrays to implement stacks and not the predefined class Stack since this makes the program extremely slow. Method stackfull is just some run-time error handling procedure.
static void hanoi(int height, char fromPole, char toPole, char withPole) { int SP, // Stack Pointer returnAddr; // return address int[] HeightStack = new [height], ReturnAddrStack = new [height]; char tmp; char[] fromStack = new [height], toStack = new [height], withstack = new [height]; int SUB = height - 1; //Stack Upper Bound SP = -1; 1: if (height>0) { SP++; // we replace the first recursive call // with this code if(SP > SUB) // check for stack overflow stackfull(); HeightStack[SP] = height; // push parameters fromStack[SP] = fromPole; // onto stack toStack[SP] = toPole; withStack[SP] = withPole; ReturnAddrStack[SP] = 2; // push return address onto stack height--; // evaluate arguments tmp = toPole; // `b' just gets the value of `c' toPole = withPole; // and `c' the value of `b' withPole = tmp; goto 1; // branch to the beginning // of the subroutine 2: move(fromPole, toPole); SP++; // here starts code for the second // recursive call if(SP > SUB) stackfull(); HeightStack[SP] = height; // push parameters fromStack[SP] = fromPole; // onto stack toStack[SP] = toPole; withStack[SP] = withPole; ReturnAddrStack[SP]=3; // push return address onto stack height--; // evaluate parameters tmp = fromPole; fromPole = withPole; withPole = tmp; goto 1; // branch to the beginning // of the subroutine } 3: if(SP >= 0) { // stacks are not empty, so we pop values height = HeightStack[SP]; fromPole = fromStack[SP]; toPole = toStack[SP]; withPole = withStack[SP]; returnAddr = ReturnAddrStack[SP]; SP--; switch(returnAddr) // use the return address from the top of the { // stack and execute a branch to this label case 2: goto 2; case 3: goto 3; } } }
Transforming the above piece of code into an equivalent without any unconditional branches is a straightforward exercise. Please note, that in the following code variable done is the general loop controller.
static void hanoi(int height, char fromPole, char toPole, char withPole) { int[] HeightStack = new int[height]; char[] fromStack = new char[height], toStack = new char[height], withStack = new char[height]; int[] ReturnAddr = new int[height]; int SP = -1; // Stack Pointer, initially empty stack int SUB = height - 1; //Stack Upper Bound int flag=1; boolean done=false; char tmp; do { switch (flag) { case 1: while (height>0) //this loop simulates { //the first unconditional branch SP++; if (SP > SUB) stackfull(); HeightStack[SP] = height; // push parameters fromStack[SP] = fromPole; // onto stacks toStack[SP] = toPole; withStack[SP] = withPole; ReturnAddr[SP] = 2; // remember return address height--; // evaluate parameters tmp = toPole; // toPole = withPole; // withPole = tmp; // } flag=3; // now height == 0 so we must pop // values from the stacks break; case 2: moveDisk(fromPole, toPole); //move a disk SP++; if (SP > SUB) stackfull(); HeightStack[SP] = height; //push parameters fromStack[SP] = fromPole; //stacks toStack[SP] = toPole; withStack[SP] = withPole; ReturnAddr[SP] = 3; //remember return address height--; // evaluate parameters tmp = fromPole; // fromPole = withPole; // withPole = tmp; // flag=1; // simulates the unconditional branch to // label “1” break; case 3: if (SP >= 0) //stack is not empty { while (SP >= 0 && flag == 3) { height = HeightStack[SP]; fromPole = fromStack[SP]; toPole = toStack[SP]; withPole = withStack[SP]; flag = ReturnAddr[SP]; SP--; } } else { done = !done; } break; } } while (!done); }