Towers of Hanoi: Recursion to iteration 2

Let us now move the states from 4 to 6 to include the processing right after entry and the processing right before exit.

The local state1 variable is also added as a parameter to the move routine and adjusted in each place.

Here is the JavaScript code.

var stackList1 = [];

function move() {
	var n1;
	var a1;
	var b1;
	var c1;
	var state1 = 0;
	while (state1 != 5) {
		if (state1 == 0) {
			n1 = stackList1[stackList1.length-5];
			a1 = stackList1[stackList1.length-4];
			b1 = stackList1[stackList1.length-3];
			c1 = stackList1[stackList1.length-2];
			state1 = stackList1[stackList1.length-1];
			state1 = 1;
			}
		else if (state1 == 1) {
			if (n1 != 0) {
				stackList1.push(n1-1);
				stackList1.push(a1);
				stackList1.push(c1);
				stackList1.push(b1);
				stackList1.push(0);
				move();
				}
			state1 = 2;
			}
		else if (state1 == 2) {
			if (n1 != 0) {
				console.log("move "+n1+" from "+a1+" to "+b1+"\n");
				}
			state1 = 3;
			}
		else if (state1 == 3) {
			if (n1 != 0) {
				stackList1.push(n1-1);
				stackList1.push(c1);
				stackList1.push(b1);
				stackList1.push(a1);
				stackList1.push(0);
				move();
				}
			state1 = 4;
			}
		else if (state1 == 4) {
			stackList1.pop();
			stackList1.pop();
			stackList1.pop();
			stackList1.pop();
			stackList1.pop();
			state1 = 5;
			}
		}
	}
stackList1.push(3);
stackList1.push("a");
stackList1.push("b");
stackList1.push("c");
stackList1.push(0);
move();

Here is the output of the JavaScript code.

move 1 from a to b

move 2 from a to c

move 1 from b to c

move 3 from a to b

move 1 from c to a

move 2 from c to b

move 1 from a to b

Finally, let us make multiple switches in the following manner.

Let us make the local variables global.
Instead of popping the values off the stack let us use the pops to restore the previous values.
When pushing values on the stack push the value of the next state after the routine would return and the current immediate state is in state2.

Here is the JavaScript code.

var stackList1 = [];
var n1 = 3;
var a1 = "a";
var b1 = "b";
var c1 = "c";
var state1 = 0;
var state2 = 1;
stackList1.push(n1);
stackList1.push(a1);
stackList1.push(b1);
stackList1.push(c1);
stackList1.push(-1);
while (true) {
	if (state1 == 0) {
		n1 = stackList1[stackList1.length-5];
		a1 = stackList1[stackList1.length-4];
		b1 = stackList1[stackList1.length-3];
		c1 = stackList1[stackList1.length-2];
		state1 = state2;
		}
	else if (state1 == 1) {
		if (n1 != 0) {
			stackList1.push(n1-1);
			stackList1.push(a1);
			stackList1.push(c1);
			stackList1.push(b1);
			stackList1.push(2);
			state1 = 0;
			state2 = 1;
			}
		else {
			state1 = 4;
			}
		}
	else if (state1 == 2) {
		if (n1 != 0) {
			console.log("move "+n1+" from "+a1+" to "+b1+"\n");
			state1 = 3;
			}
		else {
			state1 = 4;
			}
		}
	else if (state1 == 3) {
		if (n1 != 0) {
			stackList1.push(n1-1);
			stackList1.push(c1);
			stackList1.push(b1);
			stackList1.push(a1);
			stackList1.push(4);
			state1 = 0;
			state2 = 1;
			}
		else {
			state1 = 4;
			}
		}
	else if (state1 == 4) {
		state2 = stackList1.pop();
		c1 = stackList1.pop();
		b1 = stackList1.pop();
		a1 = stackList1.pop();
		n1 = stackList1.pop();
		state1 = 0;
		if (state2 == -1) {
			break;
			}
		}
	}

Here is the output of the JavaScript code.

move 1 from a to b

move 2 from a to c

move 1 from b to c

move 3 from a to b

move 1 from c to a

move 2 from c to b

move 1 from a to b

At this point, some simplifications become apparent that will now be made. These simplifications could have been made earlier, with proper insight, but will be made now.

Note that if n1 is zero then the next state is always 4 without any intervening change. This allows the case where n1 is zero to move directly from state 0 to state 4.

Below is the code with this change.

Here is the JavaScript code.

var stackList1 = [];
var n1 = 3;
var a1 = "a";
var b1 = "b";
var c1 = "c";
var state1 = 0;
var state2 = 1;
stackList1.push(n1);
stackList1.push(a1);
stackList1.push(b1);
stackList1.push(c1);
stackList1.push(-1);
while (true) {
	if (state1 == 0) {
		n1 = stackList1[stackList1.length-5];
		a1 = stackList1[stackList1.length-4];
		b1 = stackList1[stackList1.length-3];
		c1 = stackList1[stackList1.length-2];
		if (n1 == 0) {
			state1 = 4;
			}
		else {
			state1 = state2;
			}
		}
	else if (state1 == 1) {
		stackList1.push(n1-1);
		stackList1.push(a1);
		stackList1.push(c1);
		stackList1.push(b1);
		stackList1.push(2);
		state1 = 0;
		state2 = 1;
		}
	else if (state1 == 2) {
		console.log("move "+n1+" from "+a1+" to "+b1+"\n");
		state1 = 3;
		}
	else if (state1 == 3) {
		stackList1.push(n1-1);
		stackList1.push(c1);
		stackList1.push(b1);
		stackList1.push(a1);
		stackList1.push(4);
		state1 = 0;
		state2 = 1;
		}
	else if (state1 == 4) {
		state2 = stackList1.pop();
		c1 = stackList1.pop();
		b1 = stackList1.pop();
		a1 = stackList1.pop();
		n1 = stackList1.pop();
		state1 = 0;
		if (state2 == -1) {
			break;
			}
		}
	}

Here is the output of the JavaScript code.

move 1 from a to b

move 2 from a to c

move 1 from b to c

move 3 from a to b

move 1 from c to a

move 2 from c to b

move 1 from a to b

Let us compare the above iteration code with the starting recursive code. Which code is more clear?

Here is the JavaScript code.

function move(n1, a1, b1, c1) {
	if (n1 != 0) {
		move(n1-1,a1,c1,b1);
		console.log("move "+n1+" from "+a1+" to "+b1+"\n");
		move(n1-1,c1,b1,a1);
		}
	}
move(3,"a","b","c");

Here is the output of the JavaScript code.

move 1 from a to b

move 2 from a to c

move 1 from b to c

move 3 from a to b

move 1 from c to a

move 2 from c to b

move 1 from a to b

The following observations can be made.

The reasoning and correctness of the original recursive code is straightforward using inductive reasoning.
The reasoning and correctness of the iterative code is not at all clear.
Explicitly managing the runtime stack makes reasoning about the code less clear.

The correctness of the iterative version follows from making invariant transformations from the original code. This is a common technique for showing that "improved" code (e.g., more machine efficient, etc.) is correct.