The above will work nicely so long as you are certain there are no circularities in your nested hash. If there are you will get an infinite loop. To fix this you'll need to do two things:

• give each node in the hash a unique id
• check the path you have traversed to reach the node for circularities

A small addition to the above code will eliminate the problem of circularities

# %nested_hash revised to contain a circularity
my $hAA = {aaa => 1, aab => 2 };
$hAA->{aac} = $hAA;

my %nested_hash = ( a => { aa => $hAA,
                           ab => {aba => 4,
                                  abb => 5,
                                  abc => 6} },
                    b => { ba => {baa => 7,
                                  bab => 8,
                                  bac => 9},
                           bb => {bba => 10,
                                  bbb => 11,
                                  bbc => 12} } );


sub walk {
  my $node = shift;

 OUTER:
  foreach my $k (sort keys %{ $node }) {

    # replace these lines with the lines between ***
    # push @nodes, $k;
    # print join(", ", @nodes), "\n";
    # ***

    print join(", ", @nodes) . (scalar(@nodes)?', ':'');
    foreach my $kInPath (@nodes) {
      if ($k eq $kInPath) {
        print "$k ... (circularity)\n";
        next OUTER if ($k eq $kInPath);
      }
    }

    print "$k\n";
    push @nodes, $k;

    # ***

    walk( $node->{$k} ) if ref $node->{$k};
    pop @nodes;
  }
}

# outputs
a
a, aa
a, aa, aaa
a, aa, aab
a, aa, aac
a, aa, aac, aaa
a, aa, aac, aab
a, aa, aac, aac ... (circularity)
a, ab
a, ab, aba
a, ab, abb
a, ab, abc
b
b, ba
b, ba, baa
b, ba, bab
b, ba, bac
b, bb
b, bb, bba
b, bb, bbb
b, bb, bbc
[download]

Also, it is a good idea to use named variables in your for loop rather than $_, i.e. for my $k (@nodes) instead of for (@nodes). It makes things like nested for loops a bit easier to manage and protects you from some odd side effects that can result if subroutines called within a for loop don't properly localize $_.

Update: Added code to show %nested_hash with circularity

Update: Added sample output.