Tower of Hanoi: Transforming the Recursion

[This page is auto-generated; please prefer to read the article’s PDF Form.]

Tower of Hanoi: Transforming the Recursion

Nitin Verma

September 29, 2021

The well-known Tower of Hanoi problem can be described as follows. There are 3 vertical pegs numbered 1, 2 and 3, and N disks of radius 1,2,3,…,N units each having a hole in the center. Initially, all the N disks are stacked onto peg 1 in decreasing order of their radius with the largest one (radius N) at the bottom. Our goal is to shift this “tower” of N disks to peg 3 using a sequence of moves where each “move” moves one disk from top of one peg to top of another peg. A move cannot place a larger disk over a smaller one. Peg 2 can be used as an auxiliary peg.

Following is a well-known recursive algorithm to solve this problem, implemented in C. The subproblem instance recur(n,s,d,a) shifts the tower of top n disks from peg s (source) to peg d (destination) with peg a (auxiliary) serving as the auxiliary peg. The initial problem is recur(N,1,3,2).

#define MOVE(x, y) { printf("%d->%d\n", x, y); }

void recur(int n, int s, int d, int a)
{
  if(n == 1)
  {
    MOVE(s, d);
    return;
  }

  recur(n-1, s, a, d);

  MOVE(s, d);

  recur(n-1, a, d, s);
}

We will now try to write an equivalent of this recursive algorithm without using recursive calls. The recursive calls internally happen over a call-stack in which each stack-frame represents one call and stores the local state and arguments of that call. In our non-recursive equivalent, we will maintain our own stack to simulate the recursive calls, similar to how they would happen on the internal call-stack. (This kind of approach to write non-recursive equivalent of a recursive method was discussed in an earlier article titled Maintaining the Stack for Recursion [1]).

Notice that each call of recur() requires storing its 4 arguments on the call-stack; there can be upto N such calls at any point. Now we will see how recur() can be transformed into a method without parameters, hence avoiding the need to store their values.

[Next]