Re: Recursion Confusion

[BrowserUk]

A step-by-step explanation is what I am looking for.

Okay. (but you could have produced this yourself; see Devel::Trace):

C:\test>perl -d:Trace junk72.pl
>> [0] junk72.pl                     :   16: hanoi( 3, 'A', 'C', 'B' )
+;
>> [0] junk72.pl                     :    5:     my ($n, $start, $end,
+ $extra) = @_;
>> [0] junk72.pl                     :    6:     if ($n == 1) {
>> [0] junk72.pl                     :   10:         hanoi($n-1, $star
+t, $extra, $end);
>> [0] junk72.pl                     :    5:     my ($n, $start, $end,
+ $extra) = @_;
>> [0] junk72.pl                     :    6:     if ($n == 1) {
>> [0] junk72.pl                     :   10:         hanoi($n-1, $star
+t, $extra, $end);
>> [0] junk72.pl                     :    5:     my ($n, $start, $end,
+ $extra) = @_;
>> [0] junk72.pl                     :    6:     if ($n == 1) {
>> [0] junk72.pl                     :    7:         print "Move disk 
+#1 from $start to $end.";
Move disk #1 from A to C.
>> [0] junk72.pl                     :   11:         print "Move disk 
+#$n from $start to $end.";
Move disk #2 from A to B.
>> [0] junk72.pl                     :   12:         hanoi($n-1, $extr
+a, $end, $start);
>> [0] junk72.pl                     :    5:     my ($n, $start, $end,
+ $extra) = @_;
>> [0] junk72.pl                     :    6:     if ($n == 1) {
>> [0] junk72.pl                     :    7:         print "Move disk 
+#1 from $start to $end.";
Move disk #1 from C to B.
>> [0] junk72.pl                     :   11:         print "Move disk 
+#$n from $start to $end.";
Move disk #3 from A to C.
>> [0] junk72.pl                     :   12:         hanoi($n-1, $extr
+a, $end, $start);
>> [0] junk72.pl                     :    5:     my ($n, $start, $end,
+ $extra) = @_;
>> [0] junk72.pl                     :    6:     if ($n == 1) {
>> [0] junk72.pl                     :   10:         hanoi($n-1, $star
+t, $extra, $end);
>> [0] junk72.pl                     :    5:     my ($n, $start, $end,
+ $extra) = @_;
>> [0] junk72.pl                     :    6:     if ($n == 1) {
>> [0] junk72.pl                     :    7:         print "Move disk 
+#1 from $start to $end.";
Move disk #1 from B to A.
>> [0] junk72.pl                     :   11:         print "Move disk 
+#$n from $start to $end.";
Move disk #2 from B to C.
>> [0] junk72.pl                     :   12:         hanoi($n-1, $extr
+a, $end, $start);
>> [0] junk72.pl                     :    5:     my ($n, $start, $end,
+ $extra) = @_;
>> [0] junk72.pl                     :    6:     if ($n == 1) {
>> [0] junk72.pl                     :    7:         print "Move disk 
+#1 from $start to $end.";
Move disk #1 from A to C.

But, whilst that may help you wrap your head around an existing recursive implementation, it probably won't help you with writing your own recursive routines.

The trick to understanding and using recursion is to avoiding trying to 'run the loops' in your head, and instead think about the subroutine in snapshots. That is to say, imagine each of the situations (states) that could exist at the point of entry to the subroutine and then what needs to be done to move that state to the next state.

So for the routine above the are two states:

1. $n == 1

   If there is only one disc, then all that is required is to move that disc directly from the $start to the $end and exit.

2. $n != 1

   Start with the simplest situation, of $n == 2.

   In this case, there are three steps required:

   1. Move the top disc from the $start to the $extra.

      This can be achieved by pretending that there is only one disc to move and that the $extra is the $end. In this way, we can call ourselves and the first state handler (above) will do the work.

      So reduce the count to one, switch the $end for the $extra and call ourselves recursively.

   2. Move the second disc from the $start to the $end

      With the top disc out of the way (on $extra), we can now move the second disk from the $start to the $end unimpeded.

      (The print statement does the "work" for this step!)

   3. Move the top disc from the $extra to the $end

      So, again reduce the count to one; but this time, pass $extra as the $start and $end and the end.

   And the job is done for 2 discs.

For three discs, we only need to do: the above two disc procedure but from $start to $extra; followed by the one disc procedure from $start to $end; followed by the two disc procedure from $extra to $end.

And by now, you should be able to see that by passing in $n == 3, that is exactly what happens.

/c