I tried matching "^(\\s*foo\\s*)*$" against 39 "foo "s followed by a "fo" and java.util.regex.Pattern.matches does indeed go off into recursive space never to re-emerge.

Personally I think it would be acceptable for Java to throw an exception after some bounded amount of effort in matching. Especially given that Perl's new algorithm can't catch all the pathological cases.