Let's look at the problem this way. I need to move N disks from A to B; I can use C if I want.

If I have one disk, that's easy: I just move it from A to B. Done, and I didn't need C. (That's the first part.)

If I have two, then I have to move the smaller disk out of the way (to peg C), move the biggest disk to peg B, then move the smallest disk to peg B again. Generalizing, I need to move the disks on A that are "in the way" to C (thereby getting them "out of the way"), using B as a workspace if I need it, move the disk I actually want to move to B, then move the stack on C to B using A for workspace if I need it. It might be clearer like this:

sub move_disks_from_one_peg_to_another_peg_using_a_third
{
   my ($n, $peg_a, $peg_b, $peg_c) = @_;
   if ($n == 1) 
   {
      print "Move disk #1 from $peg_a to $peg_b.\n";
      return;
   } 
   else 
   {
      move_disks_from_one_peg_to_another_peg_using_a_third($n-1, $peg_
+a, $peg_c, $peg_b);
      print "Move disk #$n from $peg_a to $peg_b.\n";
      move_disks_from_one_peg_to_another_peg_using_a_third($n-1, $peg_
+c, $b, $peg_a);
      return;
   }
}
[download]

Notice that we have the necessary criteria in place for a recursive algorithm: we have a bottom-out condition (when $n == 1, move the single disk), and we have a recursive call that guarantees we reach bottom ($n is decremented on each subsequent call). This only partly solves the problem, though: the recursive algorithm has moved N-1 disks "out of the way", and we have to move them all again to put them in their final position; this is why we need the second call. This call is also guaranteed to bottom out, because it decrements $n each time it is re-called.

The four-disk solution visualization here should help a lot: the target peg in this visualization is #3; note how we have to move the top 3 disks out of the way, then put them back, and that we have to repeat this for each successively-higher layer.

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.