I see no reason to resort to recursion:

#!/usr/bin/perl -w
use strict;
my @letter= map { [ split // ] } qw( CAT DOG BIRD );
my @idx= (0) x @letter;
while( 1 ) {
    print join( "", map { $letter[$_][$idx[$_]] } 0..$#letter ), "\n";
    my $i= 0;
    while(  $i < @letter  &&  $#{$letter[$i]} < ++$idx[$i]  ) {
        $idx[$i++]= 0;
    }
    last   if  @letter <= $i;
}
[download]

        - tye (but my friends call me "Tye")