brute force but non-recursive:

my @data = qw( 000- 0101 011- 1-0-);
my @bin;
while (@data) {
  my $data = shift @data;
  if ($data =~ tr/-//) {
    my ($zero, $one) = ($data, $data);
    $zero =~ s/-/0/;
    $one =~ s/-/1/;
    unshift @data, $zero, $one;
  }
  else {
    push @bin, $data;
  }
}

print "@bin\n";
[download]

and anyway, what is your real problem? for a big subset of the ones I can imagine, maintaining your data as a list of numbers and masks can be a better solution than actually expanding the data set.