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" */
}``` #### Tuts

Tutsmaster.org provides tutorials related to tech and programmings. We are also setting up a community for the users and students.

## You may also like

Data Structure Differences

#### Difference Between Primitive and Non-Primitive Data Types

• July 22, 2019
Primitive data type: In simple terms “data type” and “primitive data type” are simply known and used as interchangeable variables. Primitive
Data Structure What is & Queries

#### What is Data Structure? Why Do We Require This?

• July 28, 2019
Question: What is Data Structure? Data is the basic factor entity that is utilized in calculation or manipulation. There are two different type