Each regular expression defines a regular language. A regular expression can be translated to a non-deterministic finite automaton (NFA) that recognizes its language. Each NFA can be translated to an equivalent deterministic finite automaton (DFA) that recognizes the same language in linear time. Each DFA can be translated to a regular grammar (see e.g. here) that generates the same regular language. A regular grammar is a particular type of context-free grammar, which implies that all regular languages are also context free.
So, if the language you want to recognize is regular, you could use a recursive-descent parser to parse it, but you would not gain anything in terms of time-complexity.
As far as I understand, the attacks you mention in your question are related to
- Naive implementations of the parsing algorithm that are not O(n).
- Extensions to regular expressions such as back-references, which make the resulting language non-regular and force one to use some ad-hoc algorithm that has an exponential worse-case complexity.
Case 1 is easily solved by using a non-naive implementation that runs in linear time: no need for recursive-descent parsers.
Case 2 depends on the extensions you want to support. If you want to use recursive descent parser your language must be context-free, so you must first check if languages defined by regular expressions with extensions like back references are context free.
These languages are not context free (see the answer to the parallel question on the Computer Science site for very good background on the topic). My intuition as to why they are not context free is that a context free grammar would need to be able to generate strings with arbitrarily long disjoint matching substrings. You can probably use the pumping lemma for context free languages to show that a context free grammar cannot do this.
Bottom line: recursive descent parsers are no use for this kind of extensions.
A pragmatic solution is to first run the fast DFA algorithm and only revert to the potentially exponential algorithm if a back-reference is encountered in the regular expression. This is mentioned here in Section Implementations and running times. Unfortunately there is very little information about this approach in the wikipedia page. If I find more details somewhere else I will add them to this answer.