I played around with your code (well, actually I used Stephens's code for simplicity) and found a solution that amazed me: If you add 'o' to the regex operators (making it '/ego') everything works as expected. Here's my code:
print doFunc("MAIN", "B(1)+C(2)") . "\n";
my ($theFunc, $rem) = @_;
my $re = &get_re($rem);
$rem =~ s/(\w+)\(($re)\)/&doFunc($1,$2)/eog;
return "func $theFunc returns <$rem>";
### When we're called with the initial
### state, return "1|2". Otherwise, return
### our input, quotemeta'd.
my ($in) = @_;
if ($in eq "B(1)+C(2)")
return quotemeta ($in);
Sorry that I can't tell you why perl is behaving like this. '/o' shouldn't
change the behavior at all (at least that's what I though) and $re doesn't change either.. Maybe perl messes up the namespaces when doing recursive calls using a regex? I really don't know..
By the way: When I'm not using the '/o' operator and trying to print to STDERR just before the regex is executed my perl (5.6.1, linux 2.4.2) coredumps on me..