I second your choice of recursion to solve this problem, but I think that the code can be simplified significantly without much loss in readability. In particular, when writing recursive functions I try to make the "base case" and the "general case" (and in particular, the "recursive step") as easy to identify as possible. Also note that Perl makes it very easy to copy hashes in one fell swoop; no need to copy the key/value pairs individually:

sub enumerate {
  # base case: return an array containing a single
  # empty anonymous hash (ref).
  return ( +{} ) unless @_;

  # general case
  my %p = @_;
  my ( $key, $val ) = each %p;
  my @ret;
  delete $p{ $key };
  for my $h ( enumerate( %p ) ) { # recursion
    for my $d ( @$val ) {
      my %c = %$h;                # copy hash
      $c{ $key } = $d;
      push @ret, \%c;
    }
  }
  return @ret;
}
[download]

the lowliest monk

I agree with Pustular Postulant that the code can be slightly simplified and that it is beneficial to clearly define the base case. In essence this problem is simply one of data structure traversal. I think you can take advantage of the fact that each hash entry is an array to simplify the problem to a 2-dimensional array traversal. Here's my code. No better than above, but a slightly different approach. I extracted the data structure to a global to simplify the code in order to highlight the traversal logic.

#!/usr/bin/perl
use strict;

my %set = (
       'foo' => [1, 2, 3],
       'bar' => ["A", "B", "C"],
       'biz' => ["Y", "Z"],
      );
my @keys = sort keys %set;
my $rows = @keys - 1;
my @RESULTSET = ();

sub enumerate {
    my $row = shift;
    my @result = @_;

    my @row_data = @{$set{$keys[$row]}};

    foreach my $data (@row_data) {

    # Base Case
     if ($row == $rows) {
        my $item;
        my @copy = (@result, $data);
        for (my $i; $i < @copy; $i++) {
        $item->{$keys[$i]} = $copy[$i];
        }
         push @RESULTSET,$item;
     }

    # Recursive Case
    enumerate($row+1, (@result, $data)) if ($row < $rows);
    }
}


enumerate(0,());
foreach my $item (@RESULTSET) {
    foreach my $key (@keys) {
    print $key ." => ". $item->{$key} .", ";
    }
    print "\n";
}
[download]

my @list = glob({'A','B','C'}{'1','2','3'}{'Y','Z'});
foreach my $item (@list)
{ printf "bar=%s, biz=%s, foo=%s\n", split //, $item }
[download]

I think you meant

printf "bar=%s, biz=%s, foo=%s\n", split //, $_
  for glob('{A,B,C}{1,2,3}{Y,Z}')
[download]

While that works in the simple case, I didn't want to add ugly delimiters when my input grows to be more complex than simple words.

So? Do a mapping. map all your words to four-character short names (take the next item from 'aaaa'..'zzzz', thanks to ++ this is easy).

Then do your glob with glob. Then map all results through a "find 4 characters and replace them with the mapping" operations. Like magic!

-- Randal L. Schwartz, Perl hacker
Be sure to read my standard disclaimer if this is a reply.

---

update: If you think about this, it's a bit like how I came up with what was later called "the Schwartzian transform". When you can't solve a problem in one space, map it to another space, do the solution, then map it back. It's a common pattern of mine for solving things.