Here is my solution. This is not a great example, as I didn't have time to really think this out, but...

use strict;
my @set = qw(A B C);
mk_tuples(2, 0, \@set, []);  # put the number of tuples first
print join "\n", map join(' ', @$_), get_tuples();

{
   my @full_builds;
   sub mk_tuples {
      my ($depth, $previous_depth, $set, $built) = @_;
      push(@full_builds, $built) if $depth == $previous_depth;

      for my $current_depth ($previous_depth..$depth) {
         for (@$set) {
            mk_tuples($depth, $previous_depth+1, $set, [@$built, $_]);
         }
      }
   }

   sub get_tuples {
      die "none made\n" unless @full_builds;
      return @full_builds;
   }
}
[download]

Hope that helps.

Update: As you can see, mine requires 4 arguments: 1) the depth to stop at, 2) the depth we are at currently, 3) the full set of possibles to iterate over, and 4) the partial_builds to be passed recursively. I know this isn't exactly what you want... Sorry.