Thinking Recursively

At Fairway we have a weekly lunch get-together called Code Club where we discuss interesting computing problems and share solutions in whatever language we choose.  The majority of the problems we’ve been solving come from Project Euler (http://projecteuler.net/) and the S-99 (http://aperiodic.net/phil/scala/s-99/).

Tower of Hanoi

Our most recent problem was to solve the Tower of Hanoi (http://en.wikipedia.org/wiki/Tower_of_Hanoi).  The Tower of Hanoi is a puzzle in which there are 4 disks of decreasing size.  These disks start stacked on the leftmost of three rods.  The goal is to move all of the disks to the rightmost rod by moving one disk at a time and obeying the only rule of the game – no disk may be placed on top of a smaller disk.

Here is the starting point of the game:

 

Here is the completed puzzle:

The following link contains a nice animation showing how to solve the puzzle: http://www.mathsisfun.com/games/towerofhanoi.html.

Approach

One of the goals of Code Club is to try out new programming languages and paradigms for solving these problems.  I have been working with Racket (http://docs.racket-lang.org), a dialect of Scheme, which itself is a dialect of Lisp.

To solve the problem using an imperative approach, one might start thinking about what loops to write to cause the disks to move according to the rules.  To successfully do this would require determining which direction each move should take so that the ultimate goal is reached.

A higher-level approach to solving this problem is to address the problem in a recursive way.  This means defining the solution in terms of itself then allowing recursion to do the heavy lifting.

To develop a recursive solution requires identifying the functions that will be needed.  For each function we must identify the inputs and output, then define the cases that must be handled.  Let’s solve this problem recursively using pseudocode first, then see an actual implementation in Racket.

Pseudocode Solution

To start, we need to define the main function that will solve the puzzle.

To solve this puzzle we need to move 4 disks from the leftmost rod to the rightmost rod.  There we go, our first function should be called move-disks.  The input will need to include the following parameters:

1. The number of disks to move
2. The rod from which the disks should be moved (from)
3. The rod to use as a temporary storage location while performing the move (spare)
4. The rod to which the disks should be moved (to)

Here is the beginning of our function definition:

move-disks(num-disks, from, spare, to):

     /* Definition goes here */

The next question to ask is, “What should move-disks return?”  Since we want to provide a solution, this function should return the sequence of moves to move the given number of disks from the “from” rod to the “to” rod.  We can think of a move as a pair of rods – the first rod in the pair is the beginning point of the disk and the second rod in the pair is the ending point.  Since a single move is a pair of rods, and this function should return a sequence of moves, this function should return a list of pairs.

Our last step is to fill in all of the cases for moving the disks.  This means identifying the base case(s) and the recursive case.

The base case occurs when there is one disk to move.  This is a simple situation in which only one move is required – directly moving the disk from its current rod to the destination rod.  Here is our new function with this case defined:

move-disks(num-disks, from, spare, to):

     if num-disks = 1: list(pair(from, to))

     /* Definition of other cases go here */

That’s it.  Now this function is called asking to move a single disk it will return a list of the moves.  Since there is only one move, the list will contain only one pair.  It’s important that we still return a list even though it only contains one pair since this function must always return the same type (a list of pairs).  If this return type is not honored consistently by all cases then we will run into difficulties trying to have this function call itself in the recursive step.

Now it’s time to define the recursive case.  If there is more than one disk to be moved, the problem can be subdivided into three steps:

1. First, move all of the disks except one (the one on the bottom) to the spare rod.
2. Second, move the single remaining disk to the destination rod.
3. Third, move the disks moved in the first step to the destination rod so they sit on the bottom disk.

Following these steps we have reduced the original problem into a series of smaller steps that will eventually arrive at the base case where we move a single disk.  This is the key to implementing a recursive solution.

Here is the full definition of move-disks with the recursive case now provided (note that the “append” function combines the contents of multiple lists into a single list):

move-disks(num-disks, from, spare, to):

     if num-disks = 1: return list(pair(from, to))

     else return append(move-disks(num-disks – 1, from, to, spare),

                        move-disks(1, from, spare, to),

                        move-disks(num-disks – 1, spare, from, to))

There are a couple of important things to note here.

First the append function takes a variable number of lists as parameters and returns the contents of those lists appended into a single list.  This combines the sequence of moves taken for each of the sub-moves into a single list of moves.

Second, the return value in this recursive case is a list of pairs of moves.  This is consistent with the return type that we said move-disks should always return so our function returns a consistent data type regardless of whether the base case or the recursive case occurs.

This solution now works.  In fact, this solution will work with any number of disks (not just 4 as described in the classic Tower of Hanoi puzzle).  Here is an example of calling this function:

move-disks(4, “rod 1”, “rod 2”, “rod 3)

If you were able to run this program it would output the series of moves to arrive at the desired solution to solve a Tower of Hanoi having 4 disks.

Racket Solution

Here is the analogous solution implemented using Racket:

(define (move-disks num-disks from spare to)

  (cond [(= num-disks 1) (list (cons from to))]

        [else (append (move-disks (- num-disks 1) from to spare)     ; Move all disks above base disk to spare rod

                      (move-disks 1 from spare to)                   ; Move base disk to destination rod

                      (move-disks (- num-disks 1) spare from to))])) ; Move all disks from spare rod to destination rod

Running the program produces the following output:

> (move-disks 4 'r1 'r2 'r3)

{{r1 . r2}

 {r1 . r3}

 {r2 . r3}

 {r1 . r2}

 {r3 . r1}

 {r3 . r2}

 {r1 . r2} 

 {r1 . r3} 

 {r2 . r3} 

 {r2 . r1}

 {r3 . r1}

 {r2 . r3}

 {r1 . r2}

 {r1 . r3}

 {r2 . r3}}

 

Conclusion

Solving problems using recursion rather than taking an imperative approach allows for more elegant solutions.  In this case, we were able to define the problem in terms of itself and avoid the need for manually determining to which rod each disk should be moved.

In general, to solve a problem recursively requires the following important steps:

1. Identify the inputs and output of the recursive function.
2. Define the base case(s) that terminate the recursion.
3. Define the recursive case(s) that break the input into a smaller form that is one step closer to a base case.
4. Ensure that all cases return the consistent output type originally identified in step 1.

Happy recurring!