Dan_Jacobson@ATT.COM (02/16/91)
[Just want to point out that there's also an implementation of Towers of Hanoi in GNU Emacs, for those who are collecting them.] -- Dan_Jacobson@ATT.COM Naperville IL USA +1 708-979-6364
pinard@IRO.UMontreal.CA (Francois Pinard) (02/16/91)
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