Tower of Hanoi is an absorbing game (sec brief description in the program). It is best implemented in languages which support recursion (a subroutine or procedure calling itself) with local variables, such as PASCAL, LOGO, or BBC (Acorn) BASIC. A LOCO version by J. Hughes appeared in TAU, March 86, and the HISOFT PASCAL manual has its own version. Our BASIC allows recursion, but does not support local variables. The problem can be overcome by programming a software stack which holds the local values while the routine is active, removing them on exit. This technique was used by Michael Byrne in his implementation in Tandy Model I BASIC, published in the (now defunct, I believe) MICRO-80. It can overcome one of the major shortcomings of traditional BASIC. Recursion is very difficult to explain. Briefly, the routine keeps on calling itself, building up the local variables and RETURNS, until a certain condition is reached. It then starts unwinding, executing the instructions which follow the GOSUB. The program has a provision for single-stepping through the disc moves and displays the stack as it is changing, and this could help to clarify the workings. The program comes in two parts: part one has the setting up routines and the recursive and manual modes, and will run as it is; part two contains two other implementations I have come across, and is intended to be merged with part one. TAU |
