# Tower of Hanoi Recursion

code:

```#include<stdio.h>
void toh(int n,int source,int aux,int dest)
{
if(n==1){
//just pick and place
printf("move the disk from tower no: %d to tower no: %d\n",source,dest);
return;
}

//move all n-1 disk to aux
toh(n-1,source,dest,aux);
toh(1,source,aux,dest);
toh(n-1,aux,source,dest);

}

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

output:

```move the disk from tower no: 1 to tower no: 3
move the disk from tower no: 1 to tower no: 2
move the disk from tower no: 3 to tower no: 2
move the disk from tower no: 1 to tower no: 3
move the disk from tower no: 2 to tower no: 1
move the disk from tower no: 2 to tower no: 3
move the disk from tower no: 1 to tower no: 3
```

Pseudocode:

```START
Procedure Hanoi(disk, source, dest, aux)

IF disk == 0, THEN
move disk from source to dest
ELSE
Hanoi(disk - 1, source, aux, dest)     // Step 1
move disk from source to dest          // Step 2
Hanoi(disk - 1, aux, dest, source)     // Step 3
END IF

END Procedure
STOP```

Formula: 2^n-1

https://en.wikipedia.org/wiki/Tower_of_Hanoi

It would be a great help, if you support by sharing :)
Author: zakilive