Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!uunet!bonnie.concordia.ca!IRO.UMontreal.CA!pinard From: pinard@IRO.UMontreal.CA (Francois Pinard) Newsgroups: comp.sources.d Subject: Re: v16i100: hanoi - Towers of Hanoi, Part01/01 Message-ID: Date: 16 Feb 91 15:39:10 GMT References: <1991Feb15.201409.9096@sparky.IMD.Sterling.COM> Sender: news@IRO.UMontreal.CA Organization: Universite' de Montre'al Lines: 44 In-Reply-To: zane@ddsw1.mcs.com's message of 15 Feb 91 20:14:09 GMT In article <1991Feb15.201409.9096@sparky.IMD.Sterling.COM> zane@ddsw1.mcs.com (Sameer Parekh) writes: X These two programs are based upon the one in the book X_The_Age_of_Intelligent_Machines by Raymond Kurzweil. (ISBN 0-262-11121-7) X X They solve the famous towers of hanoi problem recursively. This is *not* a flame, but just a few thoughts. Towers of Hanoi, and generation of Fibonacci numbers, among others, are classical examples used to teach recursive algorithms. They are quite bad examples in that sense that there are far better algorithms to solve these problems non-recursively. Fibonacci numbers are particularily infortunate, because directly using the recursion F(n+1) = F(n) + F(n-1) leads to exponential time, and it wrongly associates the idea of recursive programming with the idea of bad programming. A very simple non recursive solution for Towers of Hanoi is something like: move small disk to the right while not done begin do the only possible other move move small disk to the right end `Moving to the right' means moving to the just next right tower, or to the left tower if already on the righest one. `Doing the only possible other move' means moving the intermediate top disk on the largest top disk, so not involving the small disk. `Done' means that we achieved the final configuration. If we have N disks, this might mean that we made 2^N moves. Of course, you might replace `right' by `left' if you want to go the other way, or if the number of disks is even instead of odd, etc. Here is a gentle flame, however :-). Towers of Hanoi are used at the beginning of AI courses. It is so sad that people involuntarily teach that Artificial Intelligence prerequires lack of Natural Intelligence! -- Franc,ois Pinard ``Vivement GNU!'' pinard@iro.umontreal.ca (514) 588-4656 cp 886 L'Epiphanie (Qc) J0K 1J0 ...!uunet!iros1!pinard