figure an example arrangement of disks for the tower of hanoi complex recursive problems in the previous sections we looked at some problems that are relatively easy to solve and some graphically interesting problems that can help us gain mental model of what is happening in recursive algorithm in this section we will look at some problems that are really difficult to solve using an iterative programming style but are very elegant and easy to solve using recursion we will finish up by looking at deceptive problem that at first looks like it has an elegant recursive solution but in fact does not the towers of hanoi the tower of hanoi puzzle was invented by the french mathematician edouard lucas in he was inspired by legend that tells of hindu temple where the puzzle was presented to young priests at the beginning of timethe priests were given three poles and stack of gold diskseach disk little smaller than the one beneath it their assignment was to transfer all disks from one of the three poles to anotherwith two important constraints they could only move one disk at timeand they could never place larger disk on top of smaller one the priests worked very efficientlyday and nightmoving one disk every second when they finished their workthe legend saidthe temple would crumble into dust and the world would vanish although the legend is interestingyou need not worry about the world ending any time soon the number of moves required to correctly move tower of disks is at rate of one move per secondthat is yearsclearly there is more to this puzzle than meets the eye figure shows an example of configuration of disks in the middle of move from the first peg to the third notice thatas the rules specifythe disks on each peg are stacked so that smaller disks are always on top of the larger disks if you have not tried to solve this puzzle beforeyou should try it now you do not need fancy disks and poles- pile of books or pieces of paper will work how do we go about solving this problem recursivelyhow would you go about solving this problem at allwhat is our base caselet' think about this problem from the bottom up suppose you have tower of five disksoriginally on peg one if you already knew how to move tower of four disks to peg twoyou could then easily move the bottom disk to peg three complex recursive problems