TowersMany programmers don’t really understand recursion – it’s a fact, I’ve seen it time and time again. Even when we understand how it works, we tend to only use it by rote, on problems that we expect to have recursive solutions. For example, we know that a recursive function is the best way to traverse a tree in order – it’s in every textbook and so that is how we do it. There are other problems, that we can come up with, which have intuitively recursive solutions and we don’t have too much trouble with those. It’s when a problem is not intuitively recursive, but has a recursive solution, that is where the difference between being able to use it and really understanding it comes out. Incidentally, this also makes a very good case for the value of math skills in a programming context. Let me demonstrate by looking at Towers of Hanoi as a programming exercise.

Solving Towers Of Hanoi Intuitively

The Towers of Hanoi problem is very well understood. You have 3 pegs (A, B, C) and a number of discs (usually 8) we want to move all the discs from the source peg (peg A) to a destination peg (peg B), while always making sure that a bigger disc never ends up on top of a smaller one. It is a pretty simple puzzle and you can quickly work out the correct sequence to move the discs and solve the problem. But, what if you need to translate your solution into code? For those of you who are aware that this problem has a simple recursive solution, pretend to forget it for a second :).

Being the good problem solvers that we are, we will approach this methodically. To solve the Towers of Hanoi programmatically, we need to find a pattern that will easily lend itself to being expressed in code. While it might seem like it should be obvious (after all we can easily move the disks around to solve it) it is actually very elusive. Before reading any further, do try and come up with the most intuitive solution that you can for this problem (and don’t cheat by looking it up :)). Once you have it, try and code it to work out all the bugs, go ahead, I’ll wait :). If it took you less than an hour, you’re a much smarter developer than I am. I came up with several possible intuitive solutions and got bogged down with every one of them before I got one that worked. Here is the pattern that I noticed which produced a working solution.

  • We start with X number of discs, and assign a parity to each one depending on whether we have an odd or an even number of discs. For example, if we start with 3 discs, the smallest disc (disc 1) will be odd, the next one (disc 2) will be even, and the last one (disc 3) will be odd. But if we start with 4 discs, disc 1 will be even, disc 2 will be odd and so forth.
  • Every disc with the same parity always moves through the same pattern when it comes to their turn to be shifted. Lets assume our three pegs are A, B, and C with A being the source peg (where all discs start) and B being the destination peg (where all discs end up), I call C the pivot peg.
    • If a disc has an odd parity, it always moves in the following pattern A -> B -> C -> A etc.
    • If a disc has an even parity, it always moves like so A -> C -> B -> A etc.
  • If we capture these rules, then the last thing we need to do is to work out which disk to move on every iteration. This is simple, we always, move the smallest disk we can, that wasn’t shifted in the previous iteration.

Feel free to walk through all of this yourself, but I will save you the trouble since I coded all of it up, so I know it works :). Here are the relevant code snippets:

```ruby class IterativeHanoi include HanoiHelpers EVEN_PARITY = “even” ODD_PARITY = “odd”

def initialize(options={:discs => 8}) @discs = options[:discs] @pegs = {:from => [], :to => [], :pivot => []} @peg_array = [@pegs[:from], @pegs[:to], @pegs[:pivot]] @discs.downto(1) do |num| @pegs[:from] << num end @disc_parities = assign_parities @move_rules_by_parity = movement_rules_by_parity end end```

We initialize the class with the number of discs we want to use for our problem. We create three arrays to represent out pegs (source, destination and pivot) and fill the source array with numbers to represent out discs. In the case of 3 discs, the initial state of the problem will look like this.

-------
 1    
 2    
 3    
-------
 A B C
-------

We also assign the parities to our discs and set up all the movement rules according to the parities. The actual code to solve the problem looks like so:

```ruby def solve puts “SOLVING ITERATIVELY!!!” print_special_state “Initial State” source_peg = nil destination = nil while @pegs[:to].length != number_of(@discs) source_peg = next_source_peg(destination) destination = @move_rules_by_parity[parity_of(source_peg.last)][source_peg.object_id] shift(1.disc, :from => source_peg, :to => destination) raise unless state_valid print_state end print_special_state “Final State” end

def next_source_peg(off_limits_peg) source_peg = nil @peg_array.each do |array| next if array == off_limits_peg next if array.length == 0 source_peg = array if source_peg == nil || array.last < source_peg.last end source_peg end```

This does exactly what I described above, picks the peg with the smallest disc that we’re allowed to move and shifts the disc off that peg according to the movement rules, that we set up based on the parity of the disc. It will also print out the state of the puzzle at every step, like so:

-------
      
 2    
 3 1  
-------
 A B C
-------


-------
      
      
 3 1 2
-------
 A B C
-------

etc.

And it will raise an exception if it find that the puzzle has entered an invalid state (a bigger disc is on top of a smaller one). For the full implementation with all the helper methods, have a look on github (I am trying to remember to put more of the code I play around with up there), more specifically here is the class http://github.com/skorks/hanoi/blob/master/lib/iterative_hanoi.rb.

This is actually a pretty decent iterative algorithm. It takes the minimum number of steps to solve the problem and is reasonably simple to implement and understand. And yet, it took quite a long time to figure out the pattern, implement, debug and this is the intuitive solution. Can we do better? There are many different iterative algorithms for solving the Towers of Hanoi, the point is that all the iterative solutions are, if anything, more complex than the one above.

The Mathematical Approach

Math

If we were inclined to think in a more mathematical fashion, we might approach this problem a little differently. Lucky for us the math behind Towers of Hanoi is very well understood, but even if it wasn’t the idea is the same. Let’s have a look.

Mathematically, we want to work out a formula for how many steps ((T_n)) it takes to transfer (n) discs from the source to the destination peg. Looking at the smaller cases and counting the steps manually we see the following.

  • when (n=1), (T_n=1)
  • when (n=2), (T_n=3)
  • when (n=3), (T_n=7)
  • when (n=4), (T_n=15)

From this we can start to infer a pattern. Every time we increase the number of discs by 1, we need to double the number of steps and add 1, which means we can express the number of steps (T_n) taken to transfer (n) discs based on the number of steps taken to transfer (n-1) discs:

\(T_n=2T_{n-1}+1\) where \(n>{0}\)

What we have is a recurrence (or it would be if we added the \(T_0=0\) to it :)). Now we can find the closed form of this recurrence relation and then prove that it always holds true using induction. I am not going to do this here. If you want a more in-depth look at the maths behind Tower of Hanoi (includig the proof), I refer you to Concrete Mathematics. For our purposes here, we can go with the gut-feel and assume that our recurrence always holds true. How does this help?

Well, because we can represent out problem as a recurrence, it means we should be able to code a recursive solution for it.

The Recursive Solution

This is where we need to be able to connect our theoretical math with a practical approach to solving the problem, which brings me back to the start of this post. I believe that being able to apply the math behind a recursive function, in a practical fashion, is where the really deep understanding of recursion lies. Let’s break it down.

What if we can rewrite our recurrence in the following fashion:

(Tn=T{n-1}+1+T_{n-1})

1
2
3
4
5

<p>
  This tells us that to solve the tower for \(n\) disks (<em>which will take \(T_n\) steps</em>) we need to sove the tower for \(n-1\) disks, then solve the tower for \(1\) disk and then solve the tower for \(n-1\) disks again. You can probably already see where I am going with this, there is only a slight intuitive leap we need to make here, regarding where to transfer the disks each time. We need to transfer \(n-1\) disks from the source peg to the pivot peg, then transfer \(1\) disk from the source peg to the destination peg and then transfer \(n-1\) disks from the pivot to the destination and we're done. Here is the code:
</p>

```ruby

class RecursiveHanoi include HanoiHelpers def initialize(options={:discs => 8}) @discs = options[:discs] @pegs = {:from => [], :to => [], :pivot => []} @peg_array = [@pegs[:from], @pegs[:to], @pegs[:pivot]] @discs.downto(1) do |num| @pegs[:from] << num end end

def solve puts “SOLVING RECURSIVELY!!!” print_special_state “Initial State” move(@discs, @pegs) print_special_state “Final State” end

def move(n, pegs = {}) move((n-1).discs, :from => pegs.start_peg, :to => pegs.pivot_peg, :pivot => pegs.end_peg) if n > 1 shift(1.disc, :from => pegs.start_peg, :to => pegs.end_peg) print_state raise unless state_valid move((n-1), :from => pegs.pivot_peg, :to => pegs.end_peg, :pivot => pegs.start_peg) if n > 1 end end```

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

<p>
  Once again we need to do similar setup to initialize the puzzle, but the <em>move </em>function is the interesting one here, it is recursive and it is all that is needed to solve the problem (<em>aside from printing out the state in the middle</em>). As you can see the code is simple and there is no need to have any special handling for larger or smaller numbers of disks, the recursive nature of the function will work it out. Notice how closely the function resembles our recurrence relation from above:
</p>

<p style="text-align: center;">
  \(T_n=T_{n-1}+1+T_{n-1}\) 

  <p>
    Had we gone through the math instead of trying to find the '<em>intuitive</em>' solution we would not only have been finished much faster (<em>it took way longer to code the iterative solution than it did to do the recursive one</em>), but the solution would have been a lot simpler and cleaner (the above code is also on github, in <a href="http://github.com/skorks/hanoi" target="_blank">the same place</a>).
  </p>

  <blockquote>
    <p>
      As an aside, did you notice how expressive the recursive solution looked when written in Ruby. Things like <em>pegs.start_peg</em> and <em>shift(1.disc)</em> etc. I went to a tiny bit of effort to code things in a DSL-like fashion, <a href="http://www.artima.com/rubycs/articles/ruby_as_dsl.html" target="_blank">Ruby being really good for that</a> and it turned out pretty nice (<em>considering the tiny amount of effort involved</em>). I opened up the <em>Integer </em>and <em>Hash </em>classes to add the DSL-like features:
    </p>

    ```ruby

class Integer def disc self end alias_method :discs, :disc end

class Hash def start_peg self[:from] end

def end_peg self[:to] end

def pivot_peg self[:pivot] end end```

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

    <p>
      This made everything a lot more readable, the contrast with a $1.
    </p>
  </blockquote>

  <p>
    Recursion can be a very deep concept, functional languages are built on it, so I don't think you can ever understand it in one "<em>Aha!</em>" moment (<em>although you may have plenty of those along the way</em>). I think that what it does take, is a little mathematical grounding and then a lot of practice and it is tough to get the practice if we avoid it, or always go for the intuitive solution, like we tend to do in our day-to-day programming endeavors. This is where books such as <a href="http://www.amazon.com/Structure-Interpretation-Computer-Programs-Engineering/dp/0262011530" target="_blank">SICP</a> or even <a href="http://www.amazon.com/Little-Schemer-Daniel-P-Friedman/dp/0262560992/ref=sr_1_1?ie=UTF8&s=books&qid=1269780880&sr=1-1" target="_blank">The Little Schemer</a>, can be really valuable. I just wish I had time to read them myself :). If you have creative Towers of Hanoi solutions (<em>iterative or recursive</em>) or simply want to share your thoughts on recursion, math, etc., I'd love to hear from you.
  </p>

  <p>
    <span style="font-size: 10px; font-family: trebuchet ms;">Images by <a href="http://www.flickr.com/photos/vshioshvili/229207037/" target="_blank">shioshvili</a>, <a href="http://www.flickr.com/photos/35064820@N00/3950391591/" target="_blank">tkamenick</a> and <a href="http://www.flickr.com/photos/torley/2361164281/" target="_blank">Torley</a></span>
  </p>