./perl.hanoi1
HELLLLLOOOOOOOOOOOOO Move disk #1 from A to C.
Move disk #2 from A to B.
[download]

HELLLLLOOOOOOOOOOOOO Move disk #1 from C to B.
Move disk #3 from A to C.
[download]

HELLLLLOOOOOOOOOOOOO Move disk #1 from B to A.
Move disk #2 from B to C.
HELLLLLOOOOOOOOOOOOO Move disk #1 from A to C.
[download]

I suspect you are having trouble coming to grips with recursion. Recursion happens when a sub calls itself (either directly or indirectly). It is a powerful and elegant way of solving problems and works by "remembering" some state information on the subroutine call stack.

You will notice that the hanoi sub calls itself in two places - that's where the recursion happens. Notice that each time hanoi calls itself it does so with the first parameter set to one less that the value on entry thus the recursion eventually stops with $n ==1.

The following version that in essence dumps the call stack on each entry to hanoi and reports each exit from the sub may make it a little clearer (the entry numbers are the lines that hanoi was called from):

#!/usr/bin/perl -w
use strict;
use warnings;

my %piles = (A => [reverse 1..3], B => [], C => []);

dumpPiles ();
hanoi (scalar @{$piles{A}}, keys %piles);

sub hanoi {
   my ($n, $start, $end, $extra) = @_;
   
   dumpStack ();
   
   if ($n == 1) {
        report ($start, $end);
   } else {
        hanoi($n-1, $start, $extra, $end);
        report ($start, $end);
        hanoi($n-1, $extra, $end, $start);
   }
   
   print "Exiting<\n";
}

sub report {
    my ($start, $end) = @_;
    my $disk = pop @{$piles{$start}};

    print "Moved disk $disk from $start to $end.\n";
    push @{$piles{$end}}, $disk;
    dumpPiles ();
}

sub dumpPiles {
    for my $pile (sort keys %piles) {
        print "$pile: @{$piles{$pile}}\n";
    }
    print "\n";
}

sub dumpStack {
    my $index = 1; # Don't care where dumpStack was called so start at
+ 1
    my @stack;
    
    while ((my @params) = caller $index++) {
        unshift @stack, $params[2];
    }
    
    print "Entered> @stack\n";
}
[download]

Prints:

A: 3 2 1
B: 
C: 

Entered> 8
Entered> 8 18
Entered> 8 18 18
Moved disk 1 from A to C.
A: 3 2
B: 
C: 1

Exiting<
Moved disk 2 from A to B.
A: 3
B: 2
C: 1

Entered> 8 18 20
Moved disk 1 from C to B.
A: 3
B: 2 1
C: 

Exiting<
Exiting<
Moved disk 3 from A to C.
A: 
B: 2 1
C: 3

Entered> 8 20
Entered> 8 20 18
Moved disk 1 from B to A.
A: 1
B: 2
C: 3

Exiting<
Moved disk 2 from B to C.
A: 1
B: 
C: 3 2

Entered> 8 20 20
Moved disk 1 from A to C.
A: 
B: 
C: 3 2 1

Exiting<
Exiting<
Exiting<
[download]

---

Perl is environmentally friendly - it saves trees

First all, apologies for ruining some nice code. I have added a print statement and 4 comment points (A .. D).

#!/usr/bin/perl -w
use strict;
use warnings;

my %piles = (A => [reverse 1..3], B => [], C => []);

dumpPiles ();
hanoi (scalar @{$piles{A}}, keys %piles); #A

sub hanoi {
   my ($n, $start, $end, $extra, $recursion) = @_;
   print "Hanoi: Disk $n\n";
   if ($n == 1) { #B
        report ($start, $end, $recursion);
   } else {
        hanoi($n-1, $start, $extra, $end); #C
        report ($start, $end, $recursion);
        hanoi($n-1, $extra, $end, $start); #D
   }
}

sub report {
    my ($start, $end) = @_;
    my $disk = pop @{$piles{$start}};

    print "Moved disk $disk from $start to $end.\n";
    push @{$piles{$end}}, $disk;
    dumpPiles ();
}

sub dumpPiles {
    for my $pile (sort keys %piles) {
        print "$pile: @{$piles{$pile}}\n";
    }
}
[download]

The first hanoi call happens at point A, where the first argument (which disk to move) is equal the number of discs on pile A; namely '3'. We then move into the hanoi iterative method where the logical statement at B is false and we move to point C.

At point C we call hanoi again (note we have not called report yet, but the first argument has been decremented to '2'. This means we arrive at point B for the second time and the logical statement is still false.

We arrive at point C again, calling hanoi on disk number 1. Now the statement at B is true and the iterations begin to unravel.

Perhaps, together with the additional print statement in the code, this will help to explain things?

-=( Graq )=-

Its because you're not really following :)

#!/usr/bin/perl -w
use strict;

sub hanoi {
   warn "invoked @_";
   my ($n, $start, $end, $extra) = @_;
   if ($n == 1) {
       warn "Move disk #1 from $start to $end.";
   } else {
        hanoi($n-1, $start, $extra, $end);
        warn "Move disk #$n from $start to $end.";
        hanoi($n-1, $extra, $end, $start);
   }
}

hanoi(3, 'A', 'C', 'B');
__END__
invoked 3 A C B at hanoisub.pl line 5.
invoked 2 A B C at hanoisub.pl line 5.
invoked 1 A C B at hanoisub.pl line 5.
Move disk #1 from A to C. at hanoisub.pl line 8.
Move disk #2 from A to B. at hanoisub.pl line 11.
invoked 1 C B A at hanoisub.pl line 5.
Move disk #1 from C to B. at hanoisub.pl line 8.
Move disk #3 from A to C. at hanoisub.pl line 11.
invoked 2 B C A at hanoisub.pl line 5.
invoked 1 B A C at hanoisub.pl line 5.
Move disk #1 from B to A. at hanoisub.pl line 8.
Move disk #2 from B to C. at hanoisub.pl line 11.
invoked 1 A C B at hanoisub.pl line 5.
Move disk #1 from A to C. at hanoisub.pl line 8.
[download]

get it now?