Tower of HanoiRecursive solution for 4 discs:
Simple to solve for us humans brains (wetfatware), but boggling in computation software...
Let's 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 disks 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:
1.Move the top N-1 disks from Src to Aux (using Dst as an intermediary peg)
2.Move the bottom disks from Src to Dst
3.Move N-1 disks from Aux to Dst (using Src as an intermediary peg)
Assume there is a function Solve with for 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
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. To me the sheer simplicity of the solution is breathtaking. For N=3 it translates into
1.Move from Src to Dst
2.Move from Src to Aux
3.Move from Dst to Aux
4.Move from Src to Dst
5.Move from Aux to Src
6.Move from Aux to Dst
7.Move from Src to Dst
Of course "Move" means moving the topmost disk. For N=4 we get the following sequence
1.Move from Src to Aux
2.Move from Src to Dst
3.Move from Aux to Dst
4.Move from Src to Aux
5.Move from Dst to Src
6.Move from Dst to Aux
7.Move from Src to Aux
8.Move from Src to Dst
9.Move from Aux to Dst
10.Move from Aux to Src
11.Move from Dst to Src
12.Move from Aux to Dst
13.Move from Src to Aux
14.Move from Src to Dst
15.Move from Aux to Dst
You should find something here to extend to even numbered discs.
Here, we call it "performance standards."