algorithm design and recursion towers of hanoi one very elegant application of recursive problem solving is the solution to mathematical puzzle usually called the tower of hanoi or tower of brahma this puzzle is generally attributed to the french mathematician edouard lucaswho published an article about it in the legend surrounding the puzzle goes something like thissomewhere in remote region of the world is monastery of very devout religious order the monks have been charged with sacred task that keeps time for the universe at the beginning of all thingsthe monks were given table that supports three vertical posts on one of the posts was stack of concentric golden disks the disks are of varying radii and stacked in the shape of beautiful pyramid the monks were charged with the task of moving the disks from the first post to the third post when the monks have completed their taskall things will crumble to dust and the universe will end of courseif that' all there were to the problemthe universe would have ended long ago to maintain divine orderthe monks must abide by certain rules only one disk may be moved at time disk may not be "set aside it may only be stacked on one of the three posts larger disk may never be placed on top of smaller one versions of this puzzle were quite popular at one timeand you can still find variations on this theme in toy and puzzle stores figure depicts small version containing only eight disks the task is to move the tower from the first post to the third post using the center post as sort of temporary resting place during the process of courseyou have to follow the three sacred rules given above we want to develop an algorithm for this puzzle you can think of our algorithm either as set of steps that the monks need to carry outor as program that generates set of instructions for exampleif we label the three posts aband the instructions might start out like thismove disk from to move disk from to move disk from to this is difficult puzzle for most people to solve of coursethat is not surprisingsince most people are not trained in algorithm design the solution process is actually quite simple--if you know about recursion let' start by considering some really easy cases suppose we have version of the puzzle with only one disk moving tower consisting of single disk is simple enoughwe just remove it from and put it on problem solved okwhat if there are two disksi need to get the larger of the two disks over to post cbut the smaller one is sitting on top of it need to move the smaller disk out of the wayand can do this by moving it to post now the large disk on is cleari can move it to and then move the smaller disk from post onto post