Sometimes it’s fun to visit a classic CS problem when you’re learning a new language. Since I’m new to Swift, I wanted to tackle a pretty classic recursion problem, using unit tests. The Tower of Hanoi problem is a great introduction to recursion and once you get it.. it really demonstrates how recursion is really about breaking a larger problem down into smaller pieces.
The goal of the puzzle is to move all the disks from the leftmost peg to the rightmost peg, adhering to the following rules: Move only one disk at a time. A larger disk may not be placed ontop of a smaller disk.
Tackle by breaking the problem down
Often the problem is introduced for moving 3-5 disks. Consider the problem of moving 2 disks first.
You’re going to first move the top disk off to the middle tower, here called the buffer. Considering one tower to be a buffer is intrinsic to the solution so keep that idea in mind!
You’ll move the second, larger disk disk off to the final or destination tower.
You’ll finally move the original disk on top of the larger disk which is now on the destination tower.
A Unit Test
Unit Tests are obviously great because they let you know when you’ve finished. It makes validating an expected outcome so much easier. In this example, I’m using Quick and Nimble to unit test my Hanoi Tower problem
The key to turning this into a recursive code solution is to keep in mind that first move is really a buffer, on the way to the target of moving two disks from tower 1 to tower 3. Also, all towers can and should be used as buffers towers as the problem is broken down.
But, let’s first look at some psuedo code for the two disk problem.
Source tower: Tower 1
Target tower: Tower 3
Buffer tower: Tower 2
- Move disk count - 1 from source to the buffer.
- Move 1 disk from source to the destination.
- Move disk count - 1 from buffer to the destination.
Now, recursion always involves a function that calls itself until it has reached the end of it’s execution.. then returning from the inside calls to the earlier ones.. allowing any remaining executions to occur after the recursive call returns.
Let’s design our function.
This will serve our needs outlined above.. for each move of n number of disks.. we’ll need to specify an origin tower (here called Stack as these are essentially the data type Stack), a destination and a buffer.
Just for code completion. The Stack looks something like the following:
Now let’s fill it out the transfer function to handle n number of disks.
Hope this all makes sense. Again, the key to to break the problem down. The print statements in the solution above help to realize that you may be starting out calling the function to move n=5 disks.. but it starts making calls to move n-1 disks and disks don’t really start moving until a call to move the first disk off the origin, which is many calls into the solution, upon which you return out to all the earlier method calls to move disks from your buffer to whatever the destination is.
Also, what’s essential conceptually is to consider that the buffer is shifting for each call.
Check out my solution for this in this Github repository.