I had the same thought also (to use a recursive algorithm), but your code didn't seem complete or it didn't work the way I expected. There are certainly more Perlish ways to code this with map etc., but it works. Cartesian product of multiple lists using recursion.

use Data::Dumper;

my $letters = [qw(a b c)];
my $numbers = [1..3];
my $words   = [qw(you me)];

my $result = cartesian($letters, $numbers, $words);

print Dumper( $result );

sub cartesian {
  my ($set, @sets) = @_;

  my @expanded;

  # base case
  if ( !@sets ) {
    foreach ( @{$set} ){
      push @expanded, [$_];
    }
  }

  # recursive call
  else {
    my @product = @{ cartesian(@sets) };
    foreach my $element ( @{$set} ) {
      foreach my $product ( @product ) {
        push @expanded, [ $element, @{$product} ];
      }
    }
  }

  return \@expanded;
}
[download]