The Tower of Hanoi is a problem where we are given a tower of n number of disks, initially stacked in increasing size on one of three pegs. The objective is to transfer the entire tower to one of the other pegs (the rightmost one), moving only one disk at a time and never a larger one onto a smaller.
Its solution touches on two important topics:
recursive functions and stacks
recurrence relations
Recursive solution
Let call the three pegs Src (Source), Aux (Auxiliary) and Dst (Destination). To better understand and appreciate the following solution you should try solving the puzzle for small number of disks, say, 2,3, and, perhaps, 4. However one solves the problem, sooner or later the bottom disk will have to be moved from Src to Dst. At this point in time all the remaining disks will have to be stacked in decreasing size order on Aux. After moving the bottom disk from Src to Dst these disks will have to be moved from Aux to Dst. Therefore, for a given number N of disks, the problem appears to be solved if we know how to accomplish the following tasks:
Move the top N - 1 disks from Src to Aux (using Dst as an intermediary peg)
Move the bottom disk from Src to Dst
Move N - 1 disks from Aux to Dst (using Src as an intermediary peg)
Assume there is a function Solve with four arguments - number of disks and three pegs (source, intermediary and destination - in this order). Then the body of the function might look like
Solve(N, Src, Aux, Dst)
if N is 0
exit
else
Solve(N - 1, Src, Dst, Aux)
Move from Src to Dst
Solve(N - 1, Aux, Src, Dst)
This actually serves as the definition of the function Solve. The function is recursive in that it calls itself repeatedly with decreasing values of N until a terminating condition (in our case N = 0) has been met. For N = 3 it translates into
Move from Src to Dst
Move from Src to Aux
Move from Dst to Aux
Move from Src to Dst
Move from Aux to Src
Move from Aux to Dst
Move from Src to Dst
Of course "Move" means moving the topmost disk. For N = 4 we get the following sequence
Move from Src to Aux
Move from Src to Dst
Move from Aux to Dst
Move from Src to Aux
Move from Dst to Src
Move from Dst to Aux
Move from Src to Aux
Move from Src to Dst
Move from Aux to Dst
Move from Aux to Src
Move from Dst to Src
Move from Aux to Dst
Move from Src to Aux
Move from Src to Dst
Move from Aux to Dst
Recurrence relations
Let TN be the minimum number of moves needed to solve the puzzle with N disks. From the previous section T3 = 7 and T4 = 15. One can easily convince oneself that T2 = 3 and T1 = 1. A trained mathematician would also note that T0 = 0. Now let us try to derive a general formula.
The recursive solution above involves moving twice (N - 1) disks from one peg to another and making one additional move in between. It then follows that
TN ≤ TN-1 + 1 + TN-1 = 2TN-1 + 1
The inequality suggests that it might be possible to move N disks with fewer than 2TN-1 + 1 moves. Which is actually not the case. Indeed, when the time comes to move the bottom disk, (N - 1) smaller disks will have been moved from Src to Aux in at least TN-1 moves. Since we are trying to use as few steps as possible, we may assume that that portion of the task took exactly TN-1 moves. It takes just one move to move the biggest disk from Src to Dst. One then needs exactly TN-1 more steps to finish the task. Therefore the minimum number of moves needed to solve the puzzle with N disks equals TN-1 + 1 + TN-1 = 2TN-1 + 1 moves.
In other words,
TN = 2TN-1 + 1
Thus we can define the quantity TN as
T0 = 0
TN = 2TN-1 + 1 for N > 0
We may compute T1 = 2T0 + 1 = 1, T2 = 2T1 + 1= 3, T3 = 2T2 + 1 = 7 and so on sequentially.
The above expression is known as a recurrence relation which, as you might have noticed, is but a recursive function. TN is defined in terms of only one of its preceding values. Other recurrence relations may be more complicated, for example, f(N) = 2f(N - 1) + 3f(N - 2). Recurrence relations appear under various guises in numerous branches of Mathematics and applications.
Returning to the definition of TN, define SN = TN + 1. Then S0 = 1 and SN = TN + 1 = (2TN-1 + 1) + 1 = 2TN-1 + 2 = 2(TN-1 + 1) = 2SN-1. Which is to say that SN could be defined as
S0 = 1
SN = 2SN-1 for N > 0
The latter is solved easily in the closed (non-recurrent) form SN=2N. Wherefrom
TN = 2N - 1 for N ≥ 0.