Here's some code that works for your test data. There's an obvious bug (infinite recursion if there's a loop in your data): I'm sure you can solve that yourself.

  $hash{"0"}=["1","2","15"];
  $hash{"1"}=["3","4"];
  $hash{"2"}=["5","6"];
  $hash{"3"}=["7","8"];


  sub expand
  {
        my ($key) = @_;
        if (exists $hash{$key})
        {
              return sort { $a <=> $b } $key, map { expand($_) } @{$ha
+sh{$key}}
        }
        else
        {
              return $key
        }
  }

  my @expanded = map {[ expand $_ ]} @{$hash{0}};

  use Data::Dumper;
  print Dumper(\@expanded);
[download]

--Dave

Update: I've just realised that the if (exists ...) check is not needed: if the key doesn't exist, then an empty array will be used, automagically. so the expand function becomes:

  sub expand
  {
        my ($key) = @_;
        return sort { $a <=> $b } $key, map { expand($_) } @{$hash{$ke
+y}}
  }
[download]

Update 2: For efficiency, you probably want to move the sort outside the loop!

Update 3: For the golfers amongst us:

  sub e{@_,map{e($_)}@{@hash{@_}}}
  print Dumper[map{[sort{$a<=>$b}e$_]}@{$hash{0}}]
[download]