**Problem : **
Write a function that takes the same arguments as TOH but instead of
printing out the solution, returns the number of disc moves in solving
the problem.

int count_TOH(int n, int p1, int p2, int p3)
{
if (n>1) {
return 1 + count_TOH(n-1, p1, p3, p2) + count_TOH(n-1, p3, p2, p1);
} else return 1;
}

**Problem : **
If the only change in the rules of the Towers of Hanoi problem were that
you only had two poles instead of three, would the problem still be
solvable?

No; you need a temporary pole to work with. With only two poles, you
would be stuck after the first move.

**Problem : **
If you have a problem that has a recurrence relation of
*T*(*n*) = 2*T*(*n*/2) + 1, *T*(1) = 1, what would be an appropriate
big-O notation?

*O*(*nlogn*)
**Problem : **
CHALLENGE: Write an iterative solution to the Towers of Hanoi problem.

void TOH(int n)
{
int i;
n = 1 << n;
for (i = 1; i < n; i++) {
printf("Move top disc from %d to %d.\n",
(i&i-1)%3 + 1,
((i|i-1)+1)%3 + 1);
}
}

If

*n* is odd, it moves the stack to the third pole, but if

*n* is
even, it moves the stack to the second pole.

**Problem : **
In the iterative solution presented above, what is the purpose of the
`1 << n`? How does this relate to Towers of Hanoi?

Shifting the number

1 left by

*n* is equivalent to doing

2^{n}. Since
we go through the following for loop from 1 to less than

*n*, we're
looping

2^{n} - 1 times. This is the number of disk movements it takes
to solve the Towers of Hanoi puzzle.