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
