Fletch and splinky are right. Try this toy example and you will see it clearly:

use strict;
use warnings;

my $count = 0;
my $max_output = 7;

sub rec {
  my $hash  = shift;
  my $level = shift;
  return if $level > 1;

  while ( my ( $k, $v ) = each %$hash ) {
    exit 0 if ++$count > $max_output;   # backstop
    print "$level: $k\n";
    rec( $hash, $level + 1 );
  }
}

rec( { foo => 1, bar => 2, baz => 3 }, 0 );

__END__
0: bar
1: baz
1: foo
0: bar
1: baz
1: foo
0: bar
[download]

Notice how, when the recursion level is 1, the iterator doesn't visit 'bar' (because it was already visited at level 0). Instead, it visits the remaining keys (thereby exhausting each), and returns (since in this case, all further recursion stops at level 2). Once level 1 returns control to level 0, each starts again from the top.