Recursion in regular expressions has long been considered something akin to magic. Back in the 2010s, most developers didn't even suspect that RegEx engines could go deeper than one level of nesting. Today, in 2026, recursion is not exotic—it's a working tool for parsing balanced parentheses, nested tags, and even simple grammars. But there's a catch: without clear exit conditions, recursion in RegEx becomes a ticking time bomb that can take down a server in seconds.
Recently, an article was published on Habr where the authors thoroughly analyze the problem of infinite recursion and offer practical solutions ("Recursion in RegEx with Exit Conditions"). Let's examine how recursion works inside regular expressions, why it can "loop," and what techniques help keep it under control. No fluff, just code and real examples.
What is recursion in RegEx and why do we need it
Classic regular expressions (e.g., in JavaScript or Python's re module) cannot handle nested structures. You cannot write a pattern that finds correctly nested parentheses ((())) — the standard engine simply doesn't understand the concept of "depth." Recursion adds this capability.
In PCRE (Perl Compatible Regular Expressions), which powers the engines in PHP, R, and the third-party regex module for Python, there are special constructs:
(?R)— recursion to the whole pattern(?1),(?2)— recursion to the first, second group(?&name)— recursion to a named group
Basic pattern for balanced round brackets:
\( ( [^()] | (?R) )* \)
It says: find an opening bracket, then any number of non-parenthesis characters OR recursively call the entire pattern, then a closing bracket. Beautiful, right? But there's a hidden danger.
The main problem: infinite recursion
If you try this pattern on the string (()), it works fine: at level 2 it finds the inner brackets and exits. But what happens with the string (? The pattern starts unfolding recursion, expecting a closing bracket, and will go deeper and deeper until the stack runs out. In PCRE2, the default recursion depth is limited to 1000 levels — when the limit is reached, the engine throws an error. But if the limit is raised (and developers sometimes do that), you can get a process hang or application crash.
The authors of the Habr article give an example where a recursive pattern without an exit condition leads to catastrophic backtracking — the number of operations grows exponentially, and even a small input expression can "hang" the engine for a minute.
Exit conditions: how to stop recursion
The main idea is to force recursion to terminate when there is nothing left to recurse into or when we have reached some "terminal" state. There are several effective techniques:
1. Negative lookahead
Use (?!...) to check that there is no character ahead that would trigger recursion again. For example, for brackets you can forbid recursion if the next character is also an opening bracket, but we are already at the required depth. In practice, this is not always convenient.
2. Atomic groups and possessive quantifiers
An atomic group (?>...) prevents the engine from backtracking. If recursion went too far, the atomic group won't let it "unwind" — this limits the number of possible paths.
Example with atomic wrapper:
\( ( (?> [^()]+ ) | (?R) )* \)
Here (?> [^()]+ ) consumes all non-parenthesis characters at once, preventing the engine from trying different options. This reduces the chance of infinite backtracking, but does not solve the empty input problem.
3. Conditional construct (?(condition)yes|no)
The most reliable way is to add an explicit check: "recurse only if this is not a terminal case." In PCRE2, you can use conditional constructs together with recursion, for example:
(?P<balanced>\( (?: [^()] | (?P>balanced) )* \) )
Although PCRE does not have a built-in empty check, you can combine it with a lookahead: if after an opening bracket there is a closing bracket — do not recurse. The Habr article authors propose this pattern:
\( (?= [^()]* \) ) (?: [^()] | (?R) )* \)
It first checks that a closing bracket exists in the string at all, and only then starts recursion. If there is no closing bracket, recursion does not begin, the exit condition triggers.
Practical example: parsing nested HTML tags
Let's take a common interview task: extract the content of nested div blocks. Of course, for full-fledged HTML it's better to use parsers (BeautifulSoup, lxml), but for quick extraction from simple text, recursive RegEx can be useful.
Suppose we have this string:
<div>Hello, <div>world</div>!</div>
We want to get <div>Hello, <div>world</div>!</div> entirely (the outer block). A recursion pattern for PCRE (PHP):
$pattern = '/<div[^>]*> (?: [^<]++
| <(?!/div>) | (?R) )* <\/div>/xs';
Breakdown:
- <div[^>]*> — opening tag with attributes
- (?: ... )* — content, which can be:
- [^<]++ — any character except < (possessive for speed)
- <(?!/div>) — an opening tag < that is not followed by /div> (another tag, not a closing one)
- (?R) — recursion to the whole pattern (if a nested div is encountered)
- </div> — closing tag
The exit condition here is implicit: if a </div> is encountered without a preceding opening tag, the pattern does not match — that's the check. But what if the string contains <div> without a closing tag? Recursion starts, the engine looks for </div> and, not finding it, begins backtracking — again the risk of infinite backtracking.
The Habr article authors suggest adding a check for the existence of a closing tag using a lookahead:
$pattern = '/<div[^>]*>
(?= (?: [^<]++
| <(?!/div>) | (?R) )* <\/div> )
(?: [^<]++
| <(?!/div>) | (?R) )*
<\/div>/xs';
First, the lookahead checks that the entire sequence (including the closing tag) exists in the string. If not, there is no match, recursion stops. This adds one extra pass but prevents the catastrophic scenario.
Exit conditions in Python (regex module)
The standard re module does not support recursion. But there is the regex library by Matthew Barnett (available via pip, actively updated in 2026). It is fully compatible with PCRE and adds (?R), (?&name) syntax.
Example in Python:
import regex
# Pattern for balanced brackets with exit condition
pattern = r'''\(
(?= [^()]* \) ) # check that a closing bracket exists
(?:
[^()]++
| (?R)
)*
\)
'''
text = "( ( ) )"
match = regex.search(pattern, text, regex.VERBOSE)
print(match.group() if match else "No match")
Note the (?= [^()]* \) ) — this is the exit condition. Without it, an empty string inside brackets (()) would cause the engine to attempt recursion on an empty match and start calling (?R) infinitely. With the check, if there is no closing bracket or it is "far away," recursion does not start.
Trends in 2026: PCRE2 and security
In 2025–2026, several updates to PCRE2 (version 10.45+) were released, improving the handling of recursive patterns: new options for limiting backtracking and diagnostics were added. On Habr, the authors note that you can now set the maximum recursion depth via (*LIMIT_DEPTH=100) inside the pattern — this works even in environments where the global limit is not configured.
Example:
(*LIMIT_DEPTH=20) \( (?: [^()] | (?R) )* \)
If the depth exceeds 20, the engine stops recursion and reports an error (or returns "no match" depending on flags). This is a reliable protection against "accidental" infinite loops.
Another trend is using (?(DEFINE)...) to define "safe" recursive rules. This construct allows you to declare a group that does not participate in matching but can be called via (?&name). Exit conditions are written inside DEFINE:
(?(DEFINE)
(?<balanced> \( (?: [^()] | (?&balanced) )* \) )
)
(?&balanced)
Here there is no explicit empty check, but it can be added inside <balanced>, for example with a lookahead. The Habr article authors demonstrate exactly this approach — it is considered the most readable and maintainable.
When recursion in RegEx is evil and when it is good
Don't think recursion in regex is a universal solution. It has serious limitations:
- Performance: recursion in PCRE is a subroutine call with stack preservation. At depths >100 it can be noticeably slower than a simple parser.
- Debugging: recursive patterns are hard to read and test. One extra parenthesis and everything breaks.
- Incompleteness: RegEx is not a full parser for context-free grammars. Parsing HTML, JSON, or mathematical expressions is better left to specialized tools.
But for tasks like "extract all balanced fragments from a string" or "check bracket correctness," recursion in RegEx is an elegant and fast method. Especially if you use exit conditions and limits as described in the Habr article.
Conclusion
Recursion in regular expressions is a powerful but treacherous technique. Without proper exit conditions, it turns into an endless source of bugs and crashes. Key takeaways:
- Always check for the terminal symbol (closing bracket/tag) before starting recursion using a lookahead.
- Use atomic groups and possessive quantifiers to reduce backtracking.
- Set depth limits via
(*LIMIT_DEPTH)or engine settings. - Consider the
(?(DEFINE)...)construct to separate the description of recursion from its invocation.
If you work in Python — install the regex module instead of the standard re when recursion is needed. In PHP, R, Perl recursion is built-in. And for the most complex cases, don't hesitate to use a real parser — sometimes 20 lines of code in pyparsing work faster and more reliably than any regex.
For a detailed breakdown with live examples, read the original article: Recursion in RegEx with Exit Conditions. It was published on Habr in July 2026 and contains ready-to-use patterns that you can grab and use in your projects.
Comments