**What is the game of Tower of Hanoi?**

Tower of Hanoi consists of three pegs or towers with *n* disks placed one over the other. The objective of the puzzle is to move the stack to another peg following these simple rules.

- Only one disk can be moved at a time.
- No disk can be placed on top of the smaller disk.

**Tower of Hanoi algorithm explained**

Let’s try to solve a puzzle – Tower of Hanoi using recursion. Take an example with 2 disks: Disk 1 on top of Disk 2 at peg A. The target is to move both these disks to peg B. Move Disk 1 from peg A to peg C. Then move disk 2 from peg A to peg B and, finally, move disk 1 from peg C to peg B. This solution takes 3 steps. You can easily move this stack from peg B to any other peg using these 3 steps.

#includevoid TofH(int,char,char,char,int*);int main() {int n,m=0;printf("enter the number of disks:\n");scanf("%d",&n);TofH(n,'s','t','d',&m);printf("number of moves=%d\n",m);return 0;}void TofH(int n,char s,char t,char d,int *m) {if(n==1){printf("move disc %d from peg %c to peg %c\n",n,s,d);(*m)++;return;}else{TofH(n-1,s,d,t,m);printf("move disc %d from peg %c to peg %c\n",n,s,d);(*m)++;TofH(n-1,t,s,d,m);}}##############################################OUTPUT:enter the number of disks: 4 move disc 1 from peg s to peg t move disc 2 from peg s to peg d move disc 1 from peg t to peg d move disc 3 from peg s to peg t move disc 1 from peg d to peg s move disc 2 from peg d to peg t move disc 1 from peg s to peg t move disc 4 from peg s to peg dmove disc 1 from peg t to peg d move disc 2 from peg t to peg smove disc 1 from peg d to peg s move disc 3 from peg t to peg dmove disc 1 from peg s to peg t move disc 2 from peg s to peg d move disc 1 from peg t to peg d number of moves =15

**Tower of Hanoi maths explained **

By now, you might have identified that to move N disks from one peg to another, you need 2^{𝑁}−1. So, the number of steps almost double every time you insert another disk in the stack. Let us prove that the number of steps in 2^{𝑁}−1 For a given 𝑁 number of disks, the way to accomplish the task in a minimum number of steps is: Move the top 𝑁−1 disks to an intermediate peg. Move the bottom disk to the destination peg. Finally, move the 𝑁−1 disks from the intermediate peg to the destination peg. Therefore, the recurrence relation for this puzzle would become: 𝑎1=1,𝑎2=3;𝑎_{𝑁}=2𝑎_{𝑁}−1+1;𝑁≥2