238 CHAPTER13. ALGORITHMANALYSISANDDESIGN
Whatis thebasecaseforthisrecursive process?Noticehow a move ofndisksresultsintwo recursive moves
ofn 1 disks.Sincewearereducingnbyoneeachtime,thesizeofthetowerwilleventuallybe1.A tower
ofsize1 canbemoveddirectlybyjustmovinga singledisk;wedon’t needany recursive callstoremove
disksabove it.
Fixingupourgeneralalgorithmtoincludethebasecasegivesusa workingmoveToweralgorithm.
Let’s codeit upinPython.OurmoveTowerfunctionwillneedparameterstorepresentthesizeofthetower,
n; thesourcepost,source; thedestintationpost,dest; andthetemporaryrestingpost,temp. We anuse
anintfornandthestrings”A”,”B”,and”C”torepresenttheposts.Hereis thecodeformoveTower.
def moveTower(n, source,dest, temp):
if n == 1:
print "Movedisk from", source, "to", dest+"."
else:
moveTower(n-1,source, temp, dest)
moveTower(1,source, dest, temp)
moveTower(n-1,temp, dest, source)
Seehow easythatwas?Sometimesusingrecursioncanmake otherwisedifficultproblemsalmosttrivial.
To getthingsstarted,wejustneedtosupplyvaluesforourfourparameters.Let’s writea littlefunction
thatprintsoutinstructionsformovinga towerofsizenfrompostA topostC.
def hanoi(n):
moveTower(n, "A","C", "B")
Now we’rereadytotryit out.Herearesolutionstothethree-andfour-diskpuzzles.Youmightwantto
tracethroughthesesolutionstoconvinceyourselfthatthey work.
hanoi(3)
Move disk from A to C.
Move disk from A to B.
Move disk from C to B.
Move disk from A to C.
Move disk from B to A.
Move disk from B to C.
Move disk from A to C.
hanoi(4)
Move disk from A to B.
Move disk from A to C.
Move disk from B to C.
Move disk from A to B.
Move disk from C to A.
Move disk from C to B.
Move disk from A to B.
Move disk from A to C.
Move disk from B to C.
Move disk from B to A.
Move disk from C to A.
Move disk from B to C.
Move disk from A to B.
Move disk from A to C.
Move disk from B to C.
So,oursolutiontotheTowerofHanoiis a “trivial”algorithmrequiringonlyninelinesofcode.What
is thisproblemdoingina sectionlabeledhard problems? To answerthatquestion,wehave tolookatthe
efficiency ofoursolution.Remember, whenI talkabouttheefficiency ofanalgorithm,I meanhowmany