Tower of Hanoi: Transforming the Recursion: Recursion without Parameters

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

Recursion without Parameters

Consider the 4-tuple (n,s,d,a) formed by the arguments of recur(), which will be referred as “args-tuple”. Notice that the args-tuple for its two recursive (“child”) calls, (n − 1,s,a,d) and (n − 1,a,d,s), are simple transformations of the args-tuple (n,s,d,a) of the current (“parent”) call. Speciﬁcally, the transformation would consist of decrementing n and swapping (d,a) or (s,a) (for the ﬁrst and second recursive calls respectively). Thus, args-tuple for the child calls are easily obtainable from that of the parent’s call.

Interestingly, these transformations are reversible and hence allow obtaining back the parent’s args-tuple from the corresponding child’s args-tuple.

This suggests that we can maintain a single global 4-tuple of arguments, g, which would correspond to the arguments of the current recur() call and will be modiﬁed by appropriate transformations (as mentioned above) during recursive calls and their return. Then, method recur() would access its arguments from this global 4-tuple g and so can be made parameter-less.

typedef struct args_tuple
{
  int n;
  int s;
  int d;
  int a;
} args_tuple;

args_tuple g;

#define SWAP_g(x, y) { int t; t = g.x; g.x = g.y; g.y = t; }

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

void recur2()
{
  /* We will denote the three members s, d and a in struct g as
     g(s, d, a). Say, at the start of this method,
     g(s, d, a) = (S, D, A) */

  if(g.n == 1)
  {
    MOVE_g(s, d);
    return;
  }

  /* decrement n */
  g.n = g.n - 1;

  /* update g(s, d, a) to (S, A, D) */
  SWAP_g(d, a);
  recur2();
  /* revert above update */
  SWAP_g(d, a);

  MOVE_g(s, d);

  /* update g(s, d, a) to (A, D, S) */
  SWAP_g(s, a);
  recur2();
  /* revert above update */
  SWAP_g(s, a);

  /* revert above decrement */
  g.n = g.n + 1;
}

/* initial call */
g.n = N;
g.s = 1;
g.d = 3;
g.a = 2;
recur2();