Towers of Hanoi: Recursion to iteration 1

A recursively defined and implemented solution is elegant and easy to reason about for correctness purposes.

However, converting recursion to iteration show how the underlying runtime stack mechanism for access to local variables works. Below is a progressive example that shows one way how nontrivial recursion (i.e., more than one recursive call in a recursive function) can be converted to iteration.

As a starting point, below is a solution to the Towers of Hanoi problem for 3 disks (to reduce the amount of output for example purposes).

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 first step is as follows.

Expand the conditional statement for each part of the body.

Here is how this might be done. Note the following.

The variable n1 is not changed in the routine so the if statement can be broken into three parts.

Machine efficiency is not a concern at this point. Here is the JavaScript code.

function move(n1, a1, b1, c1) {
	if (n1 != 0) {
		move(n1-1,a1,c1,b1);
		}
	if (n1 != 0) {
		console.log("move "+n1+" from "+a1+" to "+b1+"\n");
		}
	if (n1 != 0) {
		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 next step is as follows.

Convert the body of the recursive function definition to a state machine.

Here is how this might be done. Note the following.

The states go from 0 to 3. At this point, the while loop just iterates through the states in order.

Here is the JavaScript code.

function move(n1, a1, b1, c1) {
	var state1 = 0;
	while (state1 != 3) {
		if (state1 == 0) {
			if (n1 != 0) {
				move(n1-1,a1,c1,b1);
				}
			state1 = 1;
			}
		else if (state1 == 1) {
			if (n1 != 0) {
				console.log("move "+n1+" from "+a1+" to "+b1+"\n");
				}
			state1 = 2;
			}
		else if (state1 == 2) {
			if (n1 != 0) {
				move(n1-1,c1,b1,a1);
				}
			state1 = 3;
			}
		}
	}
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

Runtime memory is often divided into the following.

Runtime stack that contains a base of global variables, module variables, etc., and parameter and local variables.
Runtime heap that contains dynamically allocated and recovered variables (stings, classes, etc.).

The next step is as follows.

Add a variable value stack (at the global level) that will replace the local variables within the recursive function. Note that the local variables include the passed parameters and any local variables in the recursive function definition.
Push actual parameters on the stack. Get these local variables from the stack. These are removed (popped) on function return. This removes the formal and actual parameters.

Here is how this might be done. Here is the JavaScript code.

var stackList1 = [];

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