Recursion – The Towers of Hanoi (ii)

It is in the instruction sheet for the original game that one finds indications for a recursive solution, stated for an arbitrary number of discs, namely:


“The Game easily teaches itself, in solving first the problem for 3, 4, and 5 disks.”

“The Game is always possible and requires double the time each time that an additional disk is placed on the tower. Anyone who knows how to solve the problem for eight disks, for example, moving the tower from peg number 1 to peg number 2, also knows how to solve it for nine disks. One first moves the eight top disks to peg number 3, then moves the ninth disk to peg number 2, and then brings the eight disks from peg number 3 to peg number 2. Now, in augmenting the tower by one disk, the number of moves is doubled, plus one, from the preceding game.”

translatTRANSLATED INTO ENGLISH FROM THE INSTRUCTION SHEET PROVIDED WITH THE GAME.  N. CLAUS (EDOUARD LUCAS), LA TOUR D’HANOÏ, VERITABLE CASSE-TÊTE ANNAMITE (1883)ed from French

It is hard to trace the original appearance of the Towers of Hanoi (ToH) solved algorithmically. It had been long used in mathematics to describe the process of induction. In a paper published in 1963, Harold McIntosh [1] discussed the use teaching large computers, in the guise of an IBM 7090. Using Lisp (arguably the first language to implement recursion), he suggests using ToH and the Chinese Ring Puzzle, both of which are “essentially recursive in nature”, making them good problems for the use of Lisp. The ToH was described in 1964 by Aiko Hormann [2] for use in Gaku, an early learning machine.

The original puzzle had ten disks, but the programming problem usually only appears with three disks – it is therefore a subset of the original problem. Why? Likely in order to make it simple to describe, and not waste computing resources at a time when they were very limited.

The basic computer science problem consists of three wooden pegs, and n discs, where n is classically equal to 3. The left outer peg contains the n discs of varying size which decrease in diameter from bottom to top. The goal of the Towers of Hanoi problem is to move all the discs from the leftmost peg to the rightmost peg, following two rules, which are the same as in the original game. The first rule states that only one disc can be moved at a time. The second rule states a larger disc cannot be placed upon a smaller disc.

At some point it became popular to use it in programming courses, especially after the addition of recursion to Algol 60, the first procedural language to have this ability. The problem can be solved in a non-recursive manner, but it is inherent in-elegant. The recursive solution is simple, and elegant, even if somewhat bemusing to the novice recurser. Here is a basic version of the Towers of Hanoi in Algol 68 (written in Genie Algol68):

PROC movedisk = (INT n, f, t) VOID:
BEGIN
   print(("move ",f," --> ",t,newline))
END;
PROC towersofhanoi = (INT n, f, t, u) VOID:
BEGIN
   IF n < 2 THEN
      movedisk(1,f,t)
   ELSE
      towersofhanoi(n-1,f,u,t);
      movedisk(1,f,t);
      towersofhanoi(n-1,u,t,f)
   FI
END;
BEGIN
   towersofhanoi(3, 1, 3, 2)
END

A SNOBOL4 version appeared in a text on programming [3] in the late 1960s.

Snobol4 code for Towers of Hanoi
SNOBOL4 code

As you can see it is super simple, and that inherently is one of the problems for understanding it.

  1. McIntosh, H.V., “An Experiment in Teaching the Use of Large Electronic Computers”, The American Mathematical Monthly, 70(2), pp.207-209 (1963) 
  2. Hormann, A., “How a computer system can learn”, IEEE Spectrum, 1(7), pp.110-119 (1964)
  3. Griswold, R.E., Poage, J.F., Polonsky, I.P., The SNOBOL4 Programming Language (2nd ed.), Prentice-Hall (1971).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.