Solving The Towers Of Hanoi Mathematically And Programmatically – The Value Of Recursion

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:

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:

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:

\(T_n=T_{n-1}+1+T_{n-1}\)

This tells us that to solve the tower for \(n\) disks (which will take \(T_n\) steps) 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:

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

Once again we need to do similar setup to initialize the puzzle, but the move function is the interesting one here, it is recursive and it is all that is needed to solve the problem (aside from printing out the state in the middle). 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:

\(T_n=T_{n-1}+1+T_{n-1}\)

Had we gone through the math instead of trying to find the 'intuitive' solution we would not only have been finished much faster (it took way longer to code the iterative solution than it did to do the recursive one), but the solution would have been a lot simpler and cleaner (the above code is also on github, in the same place).

As an aside, did you notice how expressive the recursive solution looked when written in Ruby. Things like pegs.start_peg and shift(1.disc) etc. I went to a tiny bit of effort to code things in a DSL-like fashion, Ruby being really good for that and it turned out pretty nice (considering the tiny amount of effort involved). I opened up the Integer and Hash classes to add the DSL-like features:

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

This made everything a lot more readable, the contrast with a solution written in C is quite vivid. This expressiveness made me think about the value/cost of writing more of your code in a DSL-like way. I will expand on this in a further post.

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 "Aha!" moment (although you may have plenty of those along the way). 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 SICP or even The Little Schemer, can be really valuable. I just wish I had time to read them myself :). If you have creative Towers of Hanoi solutions (iterative or recursive) or simply want to share your thoughts on recursion, math, etc., I'd love to hear from you.

Images by shioshvili, tkamenick and Torley

  • Amanda

    This discussion came up at work last week.

    I think there’s lots of value in learning to recognise the duality between recursion and iteration, and that many iterative solutions can also be seen as recursive once you take a close look at the loop invariants and loop exit conditions (which often directly match the base case and recursive case of a recursive solution).

    Some languages like ML don’t even provide looping/iterating constructs at all, and express operations on a list of things as a function of what to do with the current thing (base case) and what to do with the rest of the things (recursive case).

    And the duality is further demonstrated by compilers and languages which can optimise for tail recursion – that is, they basically take recursive functional-style calls and turn them into iterative code under the covers, so there is no stack management (and sometimes even function call) overhead. The Continuation Passing Style features in some newer languages are an attempt to make this sort of thing more explicit.

    For example, the following code will actually be an infinite loop when run on the IBM JDK, which performs tail call optimisation:

    private static int loop(int i) {
    return loop(i);
    }
    public static void main(String[] args) {
    loop(0);
    }

    But the same code on the Sun JDK will result in a StackOverflowError.

    So, I entirely agree. Whether we know it or not, our code already has a recursive nature to it, and being able to see it for what it is lets us be more expressive with it and quicker to spot correct solutions.

    • http://www.skorks.com Alan Skorkin

      Hey Amanda,

      I am actually glad you mentioned optimisation for tail recursion. The amount of stack space (and potential slowness) used by recursive functions is probably the easiest thing to point at as a case against recursion. I personally don’t think that is a valid reason for not ever looking at recursive solutions, but some might. If the compiler can do the optimisations for you though, there is no excuse :).

      • Amanda

        I think what I’m trying to say is that there is whether the semantics of your algorithm are recursive/iterative, and then there is whether your implementation is recursive/iterative, and they don’t necessarily have to be the same. With the implementation, often the difference is just whether you choose to be explicit about using a stack.

        So yes, even less of a valid reason to ignore recursion. :P

  • Korny

    While I agree with the rest of the article, I think the Towers of Hanoi is a poor choice, as it has a simple fast iterative solution, which kicks the recursive solution’s ass.

    Basically, you iterate as follows:
    * Take the ’1′ disk
    * If you have an odd number of disks, move it clockwise (i.e. move it in the order from->pivot->to->from) otherwise move it anticlockwise.
    * Look at the two pegs that don’t have the ’1′ disk on them
    * Make the only legal move between those pegs – i.e. move the smallest disk to the other peg

    I even wrote a code version of this – note I didn’t use your DSL stuff, cause I’m lazy:
    http://gist.github.com/347262

  • Pingback: Dew Drop – March 29, 2010 | Alvin Ashcraft's Morning Dew

  • ShifDee

    Korny, I remember studying that iterative procedure in school, but looking at it now, I don’t see how it’s faster than the recursive solution. For a 3-disk system, your iteration takes 10 steps vs recursion’s 7, and for 4 disks, it takes 35 vs recursions 15.

    Can you clear up why the iteration you explained is a better solution?

  • Sam

    I love your description of how to solve it! This technique of trying to work out a pattern from a few concrete (small) problem instances is very general, but it requires a lot of practice to be able to apply it effectively. A second problem that isn’t technical is ego: thinking you understand things well enough to not bother with the heavy artillery, when you actually would have saved time by just drawing the picture and a few examples in the first place to get the right solution straight away.

    You might be interested in the correspondence between SSA form and functional programming.

  • Pingback: Microsoft Interview - Minimum Number of Steps Four Robs Tower of Hanoi Question | TECH THINKER

  • ahsan arif

    wonderful