Scribd
Upload
65 views24 pages

Hanoi Towers - Recursion: Void Int Char Char Char If

The document describes the recursive algorithm for solving the Hanoi towers problem. It uses three stacks to represent the poles and recursively moves disks from the source pole to the destination pole using a spare pole, with the rules that only one disk can be moved at a time and no disk may be placed on top of a smaller disk. The algorithm works by recursively calling itself to move all but the top disk, then moving the top disk, and finally recursively calling itself again to move the remaining disks.

Uploaded by

Shubham Gupta
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
65 views24 pages

Hanoi Towers - Recursion: Void Int Char Char Char If

The document describes the recursive algorithm for solving the Hanoi towers problem. It uses three stacks to represent the poles and recursively moves disks from the source pole to the destination pole using a spare pole, with the rules that only one disk can be moved at a time and no disk may be placed on top of a smaller disk. The algorithm works by recursively calling itself to move all but the top disk, then moving the top disk, and finally recursively calling itself again to move the remaining disks.

Uploaded by

Shubham Gupta
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 24

Hanoi towers - Recursion

void solveTowers(int count, char source,


char destination, char spare) {
if (count == 1) {
printf("Move top disk from pole %c to pole %c " ,source,
,destination);
} Recursion(1)
else {
solveTowers(count-1, source, spare, destination);
Recursion(2)
solveTowers(1, source, destination, spare);
solveTowers(count-1, spare, destination, source);
} Recursion(3)
}
REC (1)

3 S D T
n Source Destination Temp

Initial Stack
REC (1)

2 S T D
3 S D T
n Source Destination Temp

Stack after recursion by line (1)


which is in the else
solveTowers(count-1, source, spare, destination);
REC (1)

1 S D T
2 S T D
3 S D T
n Source Destination Temp

Stack after recursion by line (1)


which is in the else
solveTowers(count-1, source, spare, destination);
Now, the if condition is true, so the disk will be
moved from S to D.

REC (1)

1 S D T
2 S T D
3 S D T
n Source Destination Temp

Now the recursion (1) is completed and it will move


to recursion (2) .
It will check for the top of the stack whether it is
empty or not.
REC
REC
(2)
(1)

2 S T D
3 S D T 1 S T D
n Source Destinati Temp
n Source Destinat Temp on
ion
Now the recursion (2) is started in the right side
stack for the top of the stack in left side.
Now, the if condition is true, so the disk will be
moved from S to T.

REC (2)
REC (1)

2 S T D
3 S D T 1 S T D
n Sourc Destin Temp
n Sourc Destin Temp e ation
e ation

Now the recursion (2) is completed so


it will move to recursion (3).
REC (3)
REC (1)

2 S T D
3 S D T 1 D T S
n Sourc Destin Temp
n Sourc Destin Temp e ation
e ation

Now the recursion (3) is started in the right side


stack.
Now the if condition is true for the top of the
right side stack, so the disk will be moved from D
to T.

REC (3)
REC (1)

2 S T D
3 S D T 1 D T S
n Sourc Destin Temp
n Sourc Destin Temp e ation
e ation

Now the recursion (3) is completed.


REC (3)
REC (1)

2 S T D
3 S D T 1 D T S
n Sourc Destin Temp
n Sourc Destin Temp e ation
e ation

Now the recursion (3) is completed so


it will move to next line of the
code. But there is no statement so it
will complete the process of top of
the stack of left side.
REC (1)

3 S D T
n Sourc Destin Temp
e ation

Now the stack looks like the above


and the recursion (2) starts
Now the compiler will check for the
stack. Since the stack is not empty
it will again start the process.

REC (2)
REC (1)

3 S D T 1 S D T
n Sourc Destin Temp
n Sourc Destin Temp e ation
e ation

Now the recursion (2) is started in the right side


stack.
Now the condition satisfied, so move
the disk from S to D.

REC (2)
REC (1)

3 S D T 1 S D T
n Sourc Destin Temp
n Sourc Destin Temp e ation
e ation

Now the recursion (2) is completed in the right side


stack and now it will move to recursion (3).
REC (3)
REC (1)

3 S D T 2 T D S
n Sourc Destin Temp
n Sourc Destin Temp e ation
e ation

Now the recursion (3) is started in the right side


stack.
REC REC REC
(1) (3) (1)

3 S D T 2 T D S 1 T S D
n So Des Te n Sou Dest Tem n Sou Dest Tem
urc tina mp rce inati p rce inati p
e tion on on

Now the recursion (1) is started in the third stack.


Now the if condition is true so move
the disk from T to S.

REC REC REC


(1) (3) (1)

3 S D T 2 T D S 1 T S D
n So Des Te n Sou Dest Tem n Sou Dest Tem
urc tina mp rce inati p rce inati p
e tion on on

Now the recursion (1) is completed it will move to


recursion (2).
REC REC REC
(1) (3) (2)

3 S D T 2 T D S 1 T D S
n So Des Te n Sou Dest Tem n Sou Dest Tem
urc tina mp rce inati p rce inati p
e tion on on

Now the recursion (2) is started in the third stack.


Now the if condition is true so move
the disk from T to D.

REC REC REC


(1) (3) (2)

3 S D T 2 T D S 1 T D S
n So Des Te n Sou Dest Tem n Sou Dest Tem
urc tina mp rce inati p rce inati p
e tion on on

Now the recursion (2) is completed it will move to


recursion (3).
Now the if condition is true so move
the disk from T to S.

REC REC REC


(1) (3) (3)

3 S D T 2 T D S 1 T S D
n So Des Te n Sou Dest Tem n Sou Dest Tem
urc tina mp rce inati p rce inati p
e tion on on

Now the recursion (2) is completed it will move to


recursion (3).
Now the if condition is true so move
the disk from S to D.

REC REC REC


(1) (3) (3)

3 S D T 2 T D S 1 S D T
n So Des Te n Sou Dest Tem n Sou Dest Tem
urc tina mp rce inati p rce inati p
e tion on on

Now the recursion (2) is completed it will move to


recursion (3).
REC REC
(1) (3)

3 S D T 2 T D S
n So Des Te n Sou Dest Tem
urc tina mp rce inati p
e tion on

Since all statements are completed,


the right side stack is empty.
REC
(1)

3 S D T
n Sou Dest Tem
rce inati p
on

Since all statements are completed,


the stack is empty.
For explanation and better understanding only
multiple stacks and multiple insertions are
shown.
Algorithm with two Recursion

void solveTowers(int count, char source,


char destination, char spare) {
if (count == 1) {
printf("Move top disk from pole %c to pole %c " ,source,
,destination);
}
else {
solveTowers(count-1, source, spare, destination);
printf("Move top disk from pole %c to pole %c " ,source,
,destination);

solveTowers(count-1, spare, destination, source);


}
}

You might also like