Any algorithm that uses a recursive coding style can be translated
algebraically to an algorithm that uses only loops and a stack to keep
track of state. Let's give it a try.
Recursive coding style
void move(int n, char from, char to, char hold)
{
if (n == 0) return;
else {
move(n - 1, from, hold, to);
printf("move top of %c to %c\n", from, to);
move(n - 1, hold, to, from);
}
}
You would call this with something like move(4, 'a', 'c', 'b') to get 4
disks from a to c.
To get rid of the self-calls, we need a stack to keep track of function
parameters and return locations. Each recursive call to move() is
replaced by pushing new parameter values on the stack then executiong a
'goto'. The recursive function return is implemented by popping the
stack and going to the same place in the code where execution would
have continued in the recursive version.
int main(void)
{
// stack for parameters and return labels.
struct stack_elt_t {
int n; char from, hold, to;
int rtn;
} stk[1000];
int p = 0; // stack pointer
// set up some names for top 2 stack locations
#define N stk[p].n
#define FROM stk[p].from
#define TO stk[p].to
#define HOLD stk[p].hold
#define RTN stk[p].rtn
// macro to push new params on the stack
#define PUSH(N_, FROM_, TO_, HOLD_, RTN_) \
do { struct stack_elt_t e = { N_, FROM_, HOLD_, TO_, RTN_ }; \
stk[++p] = e; } while (0)
// Set up initial parameter values.
N = 4; FROM = 'a'; TO = 'c'; HOLD = 'b';
RTN = 0;
// Our function becomes a goto target.
move:
// if statement remains the same
if (N == 0)
goto rtn; // return is a goto target, too.
else {
// equivalent of first recursive call
PUSH(N - 1, FROM, HOLD, TO, 1);
goto move;
return_from_move_1: // control returns here on pop
// no change here
printf("move top of %c to %c\n", FROM, TO);
// equivalent of second recursive call
PUSH(N - 1, HOLD, TO, FROM, 2);
goto move;
return_from_move_2: // control returns here on pop
}
rtn:
switch (stk[p--].rtn) {
case 0: break; // stack is now empty
case 1: goto return_from_move_1;
case 2: goto return_from_move_2;
}
return 0;
}
You can of course try to simplify this code including getting rid of
the gotos. Sometimes this can make the code easier to read. Sometimes
not.
Cheers!
