Tower of Hanoi

Problem with Tower of Hanoi: There are three towers given. In one of the towers, there is a certain number of disks. The problem is that we have to transfer all those disks from this tower A to tower C. The constraint is that we have to take those disks one at a time. You also have to transfer so that no larger disk is kept over a smaller disk. Tower B is used as an auxiliary tower to help us move those disks.

This problem was deemed unsolvable for a long time, but it can be solved with coding and recursion.

• If we have only one disk, move disk from tower A to tower C, tower B is auxiliary.

TOH(1, A, B, C)
  Move Disk from A to C using B

• If we have two disks, move the top disk from A to B, move the larger disk from A to C (logic for only one disk reused). Then move the disk at B to C.

TOH(2, A, B, C)
  1. TOH(1, A, C, B)
  2. Move Disk from A to C using B
  3. TOH(1, B, A, C)

• If we have three disks, we reuse the method used for two disks, but instead of moving from A to C, move it from A to B, using C as the auxiliary tower.
• Move the largest disk at A to C.
• Move the two disks at B to C, using A as the auxiliary tower.

TOH(n, A, B, C)
  1. TOH(n - 1, A, C, B)
  2. Move disk from A to C using B
  3. TOH(n - 1, B, A, C)

From this three disks procedure, we van generate the idea for N number of disks.

#include <stdio.h>

void TOH(int n, int A, int B, int C) {
  if (n > 0) {
    TOH(n - 1, A, C, B);
    printf("from %d to %d\n", A, C);
    TOH(n - 1, B, A, C);
  }
}

int main() {
  TOH(3, 1, 2, 3);
  return 0;
}

Output:

from 1 to 3
from 1 to 2
from 3 to 2
from 1 to 3
from 2 to 1
from 2 to 3
from 1 to 3

This solution is simple to read, but the performance is not good. It is taking O(2^n) time. There are no unnecessary number of steps though so it's not going to be faster, I guess.