Question

Towers of Hanoi (Recurssion)?
This is the Program. (I have understood how the game works, but not able to understand and trace out the PROGRAM for it.)
#include<stdio.h>
#include<conio.h>
void towers(int n, char source, char dest, char aux);
void main()
{
int n;
clrscr();
printf("\n Enter the number of disks:");
scanf("%d",&n);
towers(n,'A','C','B');
}
void towers(int n, char source, char dest, char aux)
{
if(n==1)
{
printf("\n Move Disk 1 from peg %c to peg %c",source,dest);
return;
}
towers(n-1,source,aux,dest);
printf("\n Move dist %d from peg %c to peg %c\n",n,source,dest);
towers(n-1,aux,dest,source);
}
Please explain how i should trace the program. Also why is the return statement required inside the IF condition? (If i dont give it, it gives me error.) .

Answer 1

#include<stdio.h>
#include<conio.h>
void towers(int n, char source, char dest, char aux);
void main()
{
    int n;
    clrscr();
    printf("\n Enter the number of disks:");
    scanf("%d",&n);
    towers(n,'A','C','B');
}
void towers(int n, char source, char dest, char aux)
{
    if(n==1)
    {
        printf("\n Move Disk 1 from peg %c to peg %c",source,dest);
        return;
    }
    towers(n-1,source,aux,dest);
    printf("\n Move dist %d from peg %c to peg %c\n",n,source,dest);
    towers(n-1,aux,dest,source);
}

The function towers(n, source, aux, dest) moves n disks from top of src(source) to dest(destination) tower and is using in the process aux (auxillary) tower.

At the beginning disks at source towers are enumerated from the top to bottom with number from 1 to n.

void towers(int n, char source, char dest, char aux) {
    // If there is just 1 disk at the source tower, then we move it to dest tower and finish and end function
    if (n == 1) {
        printf("\n Move Disk 1 from peg %c to peg %c",source,dest);
        return;
    }
    // Suppose that we have more more then 1 disk at the source tower.
    // Then we have next placement of disks: source{1, 2, ..., n - 1, n} aux{} dest{}
    // The operation towers(n - 1,source,aux,dest) moves n - 1 disks from the top of the source tower to the aux tower
    // After performing of operation we will obtain next placement of disks: source{n} aux{1, 2, ..., n - 1} dest{}
    // The operation printf("\n Move dist %d from peg %c to peg %c\n",n,source,dest);
    // The operation towers (n - 1, aux, dest, source) moves n - 1 disks from the top of the aux tower to the dest tower
    // After performing of operation we will obtain next placement of disks:
    // source{} aux{} dest {1, 2 ..., n-1, n}
    towers (n - 1, aux, dest, source);
}

The idea of the recursion is to call function for the less value to do part of operation towers for $n$ call towers for $n - 1$, towers for $n - 1$ call towers for $n - 2$ and so on. But the recursion should stop when we will reach some value (in our case is $n == 1$) and we should end all function that was called. The function which return void should end with "return; ". Hence the return statement is required inside the IF condition.

http://www.AssignmentExpert.com/