Nothing a good regex can't solve for you. No need for time consuming recursive approaches that blow up the stack. No need for off-by-one nested loops (are you sure you have enough of them?). All way to complicated. A regex can do all.

my $bases  = "ATCG";
my $length = 4;
my $q = join ";", ($bases) x $length;
my $r = join ";", ("[^;]*([^;])[^;]*") x $length;
use re 'eval';
$q =~ /^$r$(?{print "$1$2$3$4\n"})(?!)/;
[download]