That algorithm shows the possible results of a biased shuffle, not a Fisher-Yates shuffle. The random sequence generated would not be 00000 to 44444, it would be 0000 to 4321 (a five digit shuffle requires 4 iterations - the faq goes 5, but the last never swaps - with each iteration shuffling one less item).

The while loop in shuffle needs one less iteration, and a minor adjustment to recurse would look like this:

#!/usr/bin/perl
use strict;
use warnings;

my $depth = 4;
my %results;

sub recurse
{
    if (@_ == $depth) {
        shift; #discard $num
        my @deck = (1 .. $depth);
        shuffle(\@deck, [@_]);
        $results{join('', @deck)}++;
    } else {
        my $num = shift || $depth - 1;
        # one less element each iteration
        recurse($num, @_, $_) for 0 .. $num--;
    }
}

sub shuffle
{
    my($deck, $rand) = @_;
    my $i = @$deck;
    # uncomment the following line
    # print "@$rand\n";
    # pre-decrement $i instead of post - the last would be a no-op in 
+this case
    while (--$i) {
        my $j = shift @$rand;
        @$deck[$i,$j] = @$deck[$j,$i];
    }
}

recurse;
for (sort {$results{$b} <=> $results{$a}} keys %results) {
    printf "%10d %s\n", $results{$_}, $_;
}
[download]

Here are the results of the modifications, using 4 elements instead of 5 (only 24 possible permutations instead of 120 - makes the node much more readable ;):

   1 4321
   1 2143
   1 4123
   1 2413
   1 3421
   1 1324
   1 4312
   1 4231
   1 3412
   1 1432
   1 1423
   1 2431
   1 2314
   1 3214
   1 3142
   1 1342
   1 2134
   1 3241
   1 1243
   1 4213
   1 3124
   1 4132
   1 1234
   1 2341
[download]

Each possible permutation is shown exactly one time, for a possibility of being selected 1 out of 24 times (assuming a perfect rng).

Makes sense???

Update: I followed BrowserUK's link below and in that thread there is a statement that elegantly describes the problem with a biased shuffle (When the Best Solution Isn't), by blakem: "It maps 8 paths to 6 end states". In this case, it's 3125 (5**5) paths to 120 (5!) end states - assuming 5 elements to be shuffled.