Data Structure

# Tower of Hanoi Problem (TOH) with Recursive Algorithm

**TOH ( Tower of Hanoi)** is a mathematical game or puzzle. It consists of 3 pegs A, B, and C. N Disks of different diameters are placed on peg A so that a larger disk is always below a smaller disk.

The aim is to move the N disks to peg C using peg B as an auxiliary. Only the top disk on any peg may be moved to any other peg and a larger disk may never rest on a smaller one.

## A recursive algorithm for TOH,

- To move n disks from peg A to peg C, using peg B as auxiliary.
- If n==1, move the single disk from A to C
- Stop.
- Move the top n-1 disk from A to B, using C as an auxiliary.
- Move the remaining disk from A to C.
- Move the n-1 disks from B to C, using A as auxiliary.
- Tower of Hanoi

transfer(n, from, aux) { if(n==1) { move disk n 'from ' to 'to' } transfer(n-1, from, aux, to) move disk n 'from' to 'to' transfer (n-1, aux, to, from) }

To calculate the steps for a tower of Hanoi tracing follow below step,

If N = 2, steps 2^2-1 = 3 If N = 5, steps 2^5-1 = 31 N = 1, transfer (1, from, to, aux { /* from "A", to "C", aux "B" */ n==1 (true) move disk 1 'from' to 'to' /* from "A", to "C" */ }