**A) Recursive solution**

from_rod=’A’, to_rod=’B’, aux_rod=’C’, n=no of disks

def TowerOfHanoi(n ,from_rod, to_rod, aux_rod):

if n == 1:

print “Move disk 1 from rod”,from_rod,”to rod”,aux_rod

print “Move disk 1 from rod”, aux_rod, “to rod”, to_rod

return

TowerOfHanoi(n-1,from_rod, to_rod, aux_rod)

print “Move disk”,n,”from rod”,from_rod,”to rod”,aux_rod

TowerOfHanoi(n-1,from_rod, to_rod, aux_rod)

print “Move disk”,n, “from rod”, aux_rod, “to rod”, to_rod

TowerOfHanoi(n-1,from_rod, to_rod, aux_rod)

**b) Recurrence equation**

Consider 0 disks then we need 0 moves. So T(0)=0.

Now let’s derive T(n) for n disks.

First move n-1 disks from A to B => T(n-1) moves.

Move last disk from A to C => 1 move.

Then move n-1 disks from B to A => T(n-1) moves.

Move last disk from C to B => 1 move.

Now move n-1 disks from A to B => T(n-1) moves.

So we get T(n)=T(n-1)+1+T(n-1)+1+T(n-1).

Here recurrence relation is:

T(0)= 0

T(n)=3*T(n-1) + 2

**C) Complexity**

T(n)= 3*T(n-1)+2

T(1) = 2 = 3-1

T(2) = 3*2+2= 8 = 9-1

T(3) = 3*8+2 = 26 = 27-1

…

We see that

It can be easily proved using induction on n.

So it gives complexity of algorithm .

**BONUS- Python Solution**

# Recursive Python function to solve tower of hanoi

def TowerOfHanoi(n ,from_rod, to_rod, aux_rod):

if n == 1:

print “Move disk 1 from rod”,from_rod,”to rod”,aux_rod

print “Move disk 1 from rod”, aux_rod, “to rod”, to_rod

return

TowerOfHanoi(n-1,from_rod, to_rod, aux_rod)

print “Move disk”,n,”from rod”,from_rod,”to rod”,aux_rod

TowerOfHanoi(n-1,from_rod, to_rod, aux_rod)

print “Move disk”,n, “from rod”, aux_rod, “to rod”, to_rod

TowerOfHanoi(n-1,from_rod, to_rod, aux_rod)

n = 3

TowerOfHanoi(n, ‘A’, ‘B’, ‘C’)

# A, C, B are the name of rods