The last post Recursive Solution to Towers of Hanoi described the well-known recursive definition and implementation of the Towers of Hanoi problem. This post is an extension presenting the same problem iteratively by simulating the recursion stack. This implementation will simply to simulate the recursion presented on the previous post by using an explicit manual stack.
Simulate Recursion with Explicit Stack
This solution is not Towers of Hanoi specific, any recursive function containing such kind of recursive calls can be implemented in this way. To simulate the recursive nature first we need to have a look how the recursive calls are executed. Consider the recursive code snipped for Towers of Hanoi from the previous post.
void tohr (int n, char from, char to, char temp)
{
if (n > 0)
{
tohr (n-1, from, temp, to);
printf ("\n%d disk (%c -> %c)", n, from, to);
tohr (n-1, temp, to, from);
}
}
Here whenever a recursive call is made and the if block is entered (for n > 0) a recursive call is made. At recursive depth n when the value of n = 0 the if block is not entered, therefore no recursive calls are made at this level, and the control returns back the the immediately previous level (n - 1) and resumes execution from the point after the recursive function call from which the control just returned. This means that execution continues from the printf () function at level (n - 1). After calling the printf (), another recursive call is made to tohr.
If you draw the recursive call tree (as shown in the previous post), then the control flow will be a left-to-right ordering depth first traversal of the recursion tree. Therefore the control goes as deep as possible from a certain state to the deepest possible note following the left child at each state node in the recursion tree, which actually represents the execution of the first recursive call. Once a leaf in the recursion tree is found, which is the case when n = 0 (the trivial condition), the recursion rolls back to the the parent one step and chooses the next child to its right, which is basically the second recursive function call, after which the computation continues with a left-to-right depth first scan at this child.
Above, after rolling back one step and before calling the next child on its right, the printf can be called or simply any other work could be done.
The recursion will be simulated by an explicit stack which will hold the information between the calls. The depth of a function call, and the states of three variables needs to be stored in the stack. Therefore a stack element representation can be made by the following structure.
typedef struct state_t {
char from, to, temp;
int n;
} state_t;
The stack will be initialized with the initial state on the top, which has from = 'L', temp = 'T' and to = 'R'. At any level i the fist recursive call is made with the last two formal parameters at the current function swapped. Combining with the fact that while a terminal node is not found the recursive calls will be made, this section of code can be simulated by simply starting with the stack top state s, and then continue making a new state from s by swapping the to and temp fields and pushing a copy of it on the stack, while the depth value n = 0 is not reached. At each iteration the state s, with the value assignments from the previous iteration (actually, the state on the top of stack), is modified to make the next new state.
After we have reached a leaf, we need to pop off the last pushed state from the stack and then print the from and to values of the state and the to simulate the next recursive call simply swap the from and temp of the state and push this state on the stack and continue the process on previous paragraph. Note that to simulate the case of the second recursive call the state after swapping, although it should be pushed on the stack, but practically does not needs to be pushed (as in the code), as this state will be the immediately popped to be processed with the first recursive call on the next depth (the first while loop).
The simulating function is shown below.
void toh (int n)
{
state_t s;
stack_t stk;
stk_init (&stk);
/* initialize start state */
s.n = n;
s.from = 'L';
s.to = 'R';
s.temp = 'T';
/* no need to push start state `s' on the stack
* as it will be popped immediately into `s' in
* the begining of the while loop
*/
while (1)
{
/* simulate the first recursive call left most depth dive
*/
while (s.n > 0)
{
push (&stk, s);
swap (&s.to, &s.temp);
s.n--;
}
/* all the sub-problem states are expanded, problem solved
*/
if (empty (&stk))
{
break;
}
/* take the stack top into `s' which resembles the control
* return to the last level
*/
else
{
s = pop (&stk);
}
/* print the from and to before the second recursive call
*/
printf ("\n%d disk (%c -> %c)", s.n, s.from, s.to);
/* simulate the second recursive call
*/
swap (&s.temp, &s.from);
s.n--;
}
}
Note the last line makes a s.n--, this is because the end of the outer while loop resembles calling of the second function with the current state s. Formally this has to be pushed on the stack at the end, but immediately at the beginning it needs to be popped out, as it will be the next node from which the left most branch depth dive will be done. Therefore the pushing s on the stack at the end of the loop, with the value of s.n decremented by 1, and popping into s at the beginning of the next iteration is same as retaining s, therefore the redundant pushing and popping is removed from the code.
The terminating condition is when the recursion rolls back to depth 0, which is equivalent to an empty stack, that is there is no more sub-problems to be solved. It is implemented by checking if the stack is empty. I will recommend a manual execution trace comparison between the recursive implementation and this implementation.
The construction is done, now below I am including the entire code with a small stack implementation.
Sourcecode
#include <stdio.h>
#include <stdlib.h>
#define MAX_STK 128
typedef struct state_t {
char from, to, temp;
int n;
} state_t;
typedef struct _stack {
state_t arr[MAX_STK];
int top;
} stack_t;
void stk_init (stack_t *stk)
{
stk->top = -1;
}
void push (stack_t *stk, state_t val)
{
if (stk->top == (MAX_STK - 1))
{
fprintf (stderr, "\nStack Overflow\tTerminating");
exit (1);
}
stk->arr[++(stk->top)] = val;
}
state_t pop (stack_t *stk)
{
state_t s;
s.n = -1;
if (stk->top == -1)
return s;
return stk->arr[(stk->top)--];
}
int empty (stack_t *stk)
{
return (stk->top == -1);
}
void swap (char *a, char *b)
{
char t;
t = *a;
*a = *b;
*b = t;
}
void toh (int n)
{
state_t s;
stack_t stk;
stk_init (&stk);
/* initialize start state */
s.n = n;
s.from = 'L';
s.to = 'R';
s.temp = 'T';
/* no need to push start state `s' on the stack
* as it will be popped immediately into `s' in
* the begining of the while loop
*/
while (1)
{
/* simulate the first recursive call left most depth dive
*/
while (s.n > 0)
{
push (&stk, s);
swap (&s.to, &s.temp);
s.n--;
}
/* all the sub-problem states are expanded, problem solved
*/
if (empty (&stk))
{
break;
}
/* take the stack top into `s' which resembles the control
* return to the last level
*/
else
{
s = pop (&stk);
}
/* print the from and to before the second recursive call
*/
printf ("\n%d disk (%c -> %c)", s.n, s.from, s.to);
/* simulate the second recursive call
*/
swap (&s.temp, &s.from);
s.n--;
}
}
int main (void)
{
int n;
printf ("\nNumber of disks n: ");
scanf ("%d", &n);
if (n<=0)
{
printf ("\nIncorrect Input");
}
else
{
toh (n);
}
printf ("\n");
return 0;
}
Time and Space
As this is simply a simulation of the recursive implementation the growth time and space requirements will be the same as discussed in the recursive implementation. The stack size is taken as MAX_STK and which is hard coded as 128. This will allow an input of 128 without blowing the stack.
This implementation is definitely much slower than the recursive implementation because the implicit stack is much faster than the manual stack implementation. For example with 35 disks the recursive solution executes in 42 seconds, and this simulated recursion takes 367 seconds to execute for the same number of disks. Although, naturally this does not effect the growth of the execution time.
Not Purely Iterative?
I don’t know if this process can be called a purely iterative process, as this is basically an iterative implementation of the recursive definition, by simulating the implicit recursion stack manually. There are some iterative solution, which you can see in the wikipedia page Tower_of_Hanoi – Non-recursive_solution.
I’ll post the codes whenever i write the accompanying explanation and description of them.
Phoxis 
2 thoughts on “Towers of Hanoi Iterative process: simulating recursion”