Recursion issue , , , , , , , ,, , , , , , , , , ,

#1

can you explain how recursion will work

#2

@Nitin-Mishra-2380486738834604,

Tower of Hanoi consists of three pegs or towers with n disks placed one over the other.

The objective of this is to move the stack to another peg following these rules:

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

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.

Solution:
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.
Here peg A is the source, peg B is the destination and peg C is the spare peg.

For a given N number of disks, the way to accomplish the task in a minimum number of steps is:

  1. Move the top N−1 disks to a spare peg.
  2. Move the bottom disk to the destination peg.
  3. Finally, move the N−1 disks from the spare peg to the destination peg.

Example with 5 disks:
We need to move 5 disks from peg A to peg B.

Steps:

  1. Move the top 4 disks from peg A (source) to peg C (spare), using peg B (dest) as a spare peg, by recursively using the same procedure. After finishing this, we’ll have all the disks except the last disk on peg C.

  2. Now, with all the smaller disks on the spare peg, we can move the largest disk from peg A (source) to peg B (dest).

  3. Finally, we want all the disk moved from peg C (spare) to peg B (dest). We do this recursively using the same procedure again.

Code:

TOH(disk, source, dest, helper):
IF disk == 0, THEN:
   move disk from source to dest
ELSE:
TOH(disk - 1, source, helper, dest)   // Step 1 above
move disk from source to dest          // Step 2 above
TOH(disk - 1, helper, dest, source)   // Step 3 above
#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.