Write Tower of Hanoi algorithm and steps for analysis of recursive algorithm. Show the analysis of above algorithm

In this post we are discussing about Write Tower of Hanoi algorithm and steps for analysis of recursive algorithm. Show the analysis of above algorithm

Tower of Hanoi puzzle:-

In this puzzle, There are n disks of different sizes that can slide onto any of three pegs. Initially, all the disks are on the first peg in order of size, the largest on the bottom and the smallest on top. The goal is to move all the disks to the third peg, using the second one as an auxiliary, if necessary. We can move only one disk at a time, and it is forbidden to place a larger disk on top of a smaller one.

The problem has an elegant recursive solution, which is illustrated in Figure.

• To move n>1 disks from peg 1 to peg 3 (with peg 2 as auxiliary),
  • we first move recursively n-1 disks from peg 1 to peg 2 (with peg 3 as auxiliary),
  • then move the largest disk directly from peg 1 to peg 3, and,
  • finally, move recursively n-1 disks from peg 2 to peg 3 (using peg 1 as auxiliary)
• If n = 1, we move the single disk directly from the source peg to the destination peg

Figure: Recursive solution to the Tower of Hanoi puzzle The number of moves M(n) depends only on n.  The recurrence equation is

M(n) = M(n-1) + 1 + M(n-1) for n>1

We have the following recurrence relation for the number of moves M(n):

M(n) = 2M(n-1) + 1 for n>1

M(1)=1

We solve this recurrence by t e same method of backward substitutions

The pattern of the first three sums on the left suggests that the next one will be

2⁴ M(n − 4) + 2³ + 2² + 2 + 1, and generally, after i substitutions, we get

Since the initial condition is specified for n = 1, which is achieved for i = n – 1, we get the following formula for the solution to recurrence

M(n) = 2^n-1 M(n-(n-1))+2^n-1 – 1

=2^n-1 M(1) + 2^n-1 -1

=2^n-1 + 2^n-1 -1

=2ⁿ – 1