++LanX for an excellent answer (way faster than my brute force approach).

Allow me one nit-pick:

9! = 362880 possible combinations are checked in a recursive function.

Throwing in a counter shows that sub append_digit is actually called 986,410 times. Took me a while to work out why...

9! is the number of combinations if every number has exactly 9 digits. But we also allow numbers with 1, 2, ..., 8 digits. So the total number of combinations is:

my $p = 9                                   +   # 1 digit
       (9 * 8)                              +   # 2 digits
       (9 * 8 * 7)                          +   # 3 digits
       (9 * 8 * 7 * 6)                      +   # 4 digits
       (9 * 8 * 7 * 6 * 5)                  +   # 5 digits
       (9 * 8 * 7 * 6 * 5 * 4)              +   # 6 digits
       (9 * 8 * 7 * 6 * 5 * 4 * 3)          +   # 7 digits
       (9 * 8 * 7 * 6 * 5 * 4 * 3 * 2)      +   # 8 digits
       (9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1);     # 9 digits

say $p; # = 986,409
[download]

(That 1 extra sub call is the first one, when @number is empty.)

:-)

my $calls = 0;
my $count = 0;
my @digits;
my @solutions;

append_digit();

print "count: $count\n", join("\n", @solutions), "\n";
print "recursive calls: ", $calls, "\n";

sub append_digit
{
    ++$calls;
    my $number = join '', @digits;

    if (@digits && ! grep { $number % $_ } @digits)
    {
        print "$count: $number\n" unless ++$count % 100;
        push @solutions, $number;
    }

    for my $digit (1 .. 9)
    {
        next if $digit ~~ @digits;

        push @digits, $digit;
        append_digit();
        pop  @digits;
    }
}
[download]