CINXE.COM

<!DOCTYPE html> <html lang="en"><head><meta charset="utf-8"><link rel=canonical href='https://https://www.regular-expressions.info//recurse.html'><title>Regular Expression Recursion</title> <meta name="viewport" content="width=device-width, initial-scale=1"> <meta name="author" content="Jan Goyvaerts"> <meta name="description" content=""> <meta name="keywords" content=""> <link rel=stylesheet href="regex.css" type="text/css"><script src="theme.js" type="text/javascript"></script><link rel="alternate" type="application/rss+xml" title="New at Regular-Expressions.info" href="updates.xml"> </head> <body bgcolor=white text=black> <div id=top></div> <div id=btntop><div id=btngrid><a href="quickstart.html" target="_top"><div>Quick Start</div></a><a href="tutorial.html" target="_top"><div>Tutorial</div></a><a href="tools.html" target="_top"><div>Tools & Languages</div></a><a href="examples.html" target="_top"><div>Examples</div></a><a href="refflavors.html" target="_top"><div>Reference</div></a><a href="books.html" target="_top"><div>Book Reviews</div></a></div></div> <div id=contents><div id=side> <TABLE CLASS=side CELLSPACING=0 CELLPADDING=4><TR><TD CLASS=sideheader>Regex Tutorial</TD></TR><TR><TD><A HREF="tutorial.html" TARGET=_top>Introduction</A></TD></TR><TR><TD><A HREF="tutorialcnt.html" TARGET=_top>Table of Contents</A></TD></TR><TR><TD><A HREF="characters.html" TARGET=_top>Special Characters</A></TD></TR><TR><TD><A HREF="nonprint.html" TARGET=_top>Non-Printable Characters</A></TD></TR><TR><TD><A HREF="engine.html" TARGET=_top>Regex Engine Internals</A></TD></TR><TR><TD><A HREF="charclass.html" TARGET=_top>Character Classes</A></TD></TR><TR><TD><A HREF="charclasssubtract.html" TARGET=_top>Character Class Subtraction</A></TD></TR><TR><TD><A HREF="charclassintersect.html" TARGET=_top>Character Class Intersection</A></TD></TR><TR><TD><A HREF="shorthand.html" TARGET=_top>Shorthand Character Classes</A></TD></TR><TR><TD><A HREF="dot.html" TARGET=_top>Dot</A></TD></TR><TR><TD><A HREF="anchors.html" TARGET=_top>Anchors</A></TD></TR><TR><TD><A HREF="wordboundaries.html" TARGET=_top>Word Boundaries</A></TD></TR><TR><TD><A HREF="alternation.html" TARGET=_top>Alternation</A></TD></TR><TR><TD><A HREF="optional.html" TARGET=_top>Optional Items</A></TD></TR><TR><TD><A HREF="repeat.html" TARGET=_top>Repetition</A></TD></TR><TR><TD><A HREF="brackets.html" TARGET=_top>Grouping & Capturing</A></TD></TR><TR><TD><A HREF="backref.html" TARGET=_top>Backreferences</A></TD></TR><TR><TD><A HREF="backref2.html" TARGET=_top>Backreferences, part 2</A></TD></TR><TR><TD><A HREF="named.html" TARGET=_top>Named Groups</A></TD></TR><TR><TD><A HREF="backrefrel.html" TARGET=_top>Relative Backreferences</A></TD></TR><TR><TD><A HREF="branchreset.html" TARGET=_top>Branch Reset Groups</A></TD></TR><TR><TD><A HREF="freespacing.html" TARGET=_top>Free-Spacing & Comments</A></TD></TR><TR><TD><A HREF="unicode.html" TARGET=_top>Unicode</A></TD></TR><TR><TD><A HREF="modifiers.html" TARGET=_top>Mode Modifiers</A></TD></TR><TR><TD><A HREF="atomic.html" TARGET=_top>Atomic Grouping</A></TD></TR><TR><TD><A HREF="possessive.html" TARGET=_top>Possessive Quantifiers</A></TD></TR><TR><TD><A HREF="lookaround.html" TARGET=_top>Lookahead & Lookbehind</A></TD></TR><TR><TD><A HREF="lookaround2.html" TARGET=_top>Lookaround, part 2</A></TD></TR><TR><TD><A HREF="keep.html" TARGET=_top>Keep Text out of The Match</A></TD></TR><TR><TD><A HREF="conditional.html" TARGET=_top>Conditionals</A></TD></TR><TR><TD><A HREF="balancing.html" TARGET=_top>Balancing Groups</A></TD></TR><TR><TD><A HREF="recurse.html" TARGET=_top>Recursion</A></TD></TR><TR><TD><A HREF="subroutine.html" TARGET=_top>Subroutines</A></TD></TR><TR><TD><A HREF="recurseinfinite.html" TARGET=_top>Infinite Recursion</A></TD></TR><TR><TD><A HREF="recurserepeat.html" TARGET=_top>Recursion & Quantifiers</A></TD></TR><TR><TD><A HREF="recursecapture.html" TARGET=_top>Recursion & Capturing</A></TD></TR><TR><TD><A HREF="recursebackref.html" TARGET=_top>Recursion & Backreferences</A></TD></TR><TR><TD><A HREF="recursebacktrack.html" TARGET=_top>Recursion & Backtracking</A></TD></TR><TR><TD><A HREF="posixbrackets.html" TARGET=_top>POSIX Bracket Expressions</A></TD></TR><TR><TD><A HREF="zerolength.html" TARGET=_top>Zero-Length Matches</A></TD></TR><TR><TD><A HREF="continue.html" TARGET=_top>Continuing Matches</A></TD></TR> </TABLE><TABLE CLASS=side CELLSPACING=0 CELLPADDING=4><TR><TD CLASS=sideheader>More on This Site</TD></TR><TR><TD><A HREF="index.html" TARGET=_top>Introduction</A></TD></TR><TR><TD><A HREF="quickstart.html" TARGET=_top>Regular Expressions Quick Start</A></TD></TR><TR><TD><A HREF="tutorial.html" TARGET=_top>Regular Expressions Tutorial</A></TD></TR><TR><TD><A HREF="replacetutorial.html" TARGET=_top>Replacement Strings Tutorial</A></TD></TR><TR><TD><A HREF="tools.html" TARGET=_top>Applications and Languages</A></TD></TR><TR><TD><A HREF="examples.html" TARGET=_top>Regular Expressions Examples</A></TD></TR><TR><TD><A HREF="refflavors.html" TARGET=_top>Regular Expressions Reference</A></TD></TR><TR><TD><A HREF="refreplace.html" TARGET=_top>Replacement Strings Reference</A></TD></TR><TR><TD><A HREF="books.html" TARGET=_top>Book Reviews</A></TD></TR><TR><TD><A HREF="print.html" TARGET=_top>Printable PDF</A></TD></TR><TR><TD><A HREF="about.html" TARGET=_top>About This Site</A></TD></TR><TR><TD><A HREF="updates.html" TARGET=_top>RSS Feed & Blog</A></TD></TR></TABLE></DIV><div class=bodytext><div class=topad style="height:130px"><A HREF="https://www.regexbuddy.com/create.html" TARGET="_top"><picture><source media="(max-width: 370px)" srcset="ads/320/rxbtutorial100.png 1x, ads/320/rxbtutorial150.png 1.5x, ads/320/rxbtutorial200.png 2x, ads/320/rxbtutorial250.png 2.5x, ads/320/rxbtutorial300.png 3x, ads/320/rxbtutorial350.png 3.5x, ads/320/rxbtutorial400.png 4x"><source media="(max-width: 500px)" srcset="ads/360/rxbtutorial100.png 1x, ads/360/rxbtutorial150.png 1.5x, ads/360/rxbtutorial200.png 2x, ads/360/rxbtutorial250.png 2.5x, ads/360/rxbtutorial300.png 3x, ads/360/rxbtutorial350.png 3.5x, ads/360/rxbtutorial400.png 4x"><source media="(max-width: 660px)" srcset="ads/480/rxbtutorial100.png 1x, ads/480/rxbtutorial150.png 1.5x, ads/480/rxbtutorial200.png 2x, ads/480/rxbtutorial250.png 2.5x, ads/480/rxbtutorial300.png 3x, ads/480/rxbtutorial350.png 3.5x, ads/480/rxbtutorial400.png 4x"><source media="(max-width: 747px)" srcset="ads/640/rxbtutorial100.png 1x, ads/640/rxbtutorial150.png 1.5x, ads/640/rxbtutorial200.png 2x, ads/640/rxbtutorial250.png 2.5x, ads/640/rxbtutorial300.png 3x, ads/640/rxbtutorial350.png 3.5x, ads/640/rxbtutorial400.png 4x"><img src="ads/728/rxbtutorial100.png" srcset="ads/728/rxbtutorial100.png 1x, ads/728/rxbtutorial125.png 1.25x, ads/728/rxbtutorial150.png 1.5x, ads/728/rxbtutorial175.png 1.75x, ads/728/rxbtutorial200.png 2x, ads/728/rxbtutorial250.png 2.5x, ads/728/rxbtutorial300.png 3x, ads/728/rxbtutorial350.png 3.5x, ads/728/rxbtutorial400.png 4x" alt="RegexBuddy鈥擝etter than a regular expression tutorial!"></picture></A></div> <div class=bulb><h1>Regular Expression Recursion</h1><script type="text/javascript">showbulb();</script></div> <A HREF="perl.html" TARGET="_top">Perl 5.10</A>, <A HREF="pcre.html" TARGET="_top">PCRE 4.0</A>, <A HREF="ruby.html" TARGET="_top">Ruby 2.0</A>, and all later versions of these three, support regular expression recursion. Perl uses the syntax <TT CLASS=code>(?R)</TT> with <TT CLASS=code>(?0)</TT> as a synonym. Ruby 2.0 uses <TT CLASS=code>\g<0></TT>. PCRE supports all three as of version 7.7. Earlier versions supported only the Perl syntax (which Perl actually copied from PCRE). Recent versions of <A HREF="delphi.html" TARGET="_top">Delphi</A>, <A HREF="php.html" TARGET="_top">PHP</A>, and <A HREF="rlanguage.html" TARGET="_top">R</A> also support all three, as their regex functions are based on PCRE. <a href="jgsoft.html#v2">JGsoft V2</a> also supports all variations of regex recursion. While Ruby 1.9 does not have any syntax for regex recursion, it does support <A HREF="subroutine.html" TARGET="_top">capturing group recursion</A>. So you could recurse the whole regex in Ruby 1.9 if you wrap the whole regex in a capturing group. <A HREF="dotnet.html" TARGET="_top">.NET</A> does not support recursion, but it supports <A HREF="balancing.html" TARGET="_top">balancing groups</A> that can be used instead of recursion to match balanced constructs. As we鈥檒l see later, there are differences in how Perl, PCRE, and Ruby deal with <A HREF="recursebackref.html" TARGET="_top">backreferences</A> and <A HREF="recursebacktrack.html" TARGET="_top">backtracking</A> during recursion. While they copied each other鈥檚 syntax, they did not copy each other鈥檚 behavior. JGsoft V2, however, copied their syntax and their behavior. So JGsoft V2 has three different ways of doing regex recursion, which you choose by using a different syntax. But these differences do not come into play in the basic example on this page. <A HREF="boost.html" TARGET="_top">Boost</A> 1.42 copied the syntax from Perl. But its implementation is marred by bugs. Boost 1.60 attempted to fix the behavior of <A HREF="recurserepeat.html" TARGET="_top">quantifiers on recursion</A>, but it鈥檚 still quite different from other flavors and incompatible with previous versions of Boost. Boost 1.64 finally stopped crashing upon <A HREF="recurseinfinite.html" TARGET="_top">infinite recursion</A>. But recursion of the whole regex still attempts only the first alternative. <h2>Simple Recursion</h2> The regexes <TT CLASS=syntax>a(?R)?z</TT>, <TT CLASS=syntax>a(?0)?z</TT>, and <TT CLASS=syntax>a\g<0>?z</TT> all match one or more letters <tt class=match>a</tt> followed by exactly the same number of letters <tt class=match>z</tt>. Since these regexes are functionally identical, we鈥檒l use the syntax with R for recursion to see how this regex matches the string <tt class=match>aaazzz</tt>. First, <TT CLASS=syntax>a</TT> matches the first <tt class=match>a</tt> in the string. Then the regex engine reaches <TT CLASS=syntax>(?R)</TT>. This tells the engine to attempt the whole regex again at the present position in the string. Now, <TT CLASS=syntax>a</TT> matches the second <tt class=match>a</tt> in the string. The engine reaches <TT CLASS=syntax>(?R)</TT> again. On the second recursion, <TT CLASS=syntax>a</TT> matches the third <tt class=match>a</tt>. On the third recursion, <TT CLASS=syntax>a</TT> fails to match the first <tt class=string>z</tt> in the string. This causes <TT CLASS=syntax>(?R)</TT> to fail. But the regex uses a quantifier to make <TT CLASS=syntax>(?R)</TT> <A HREF="optional.html" TARGET="_top">optional</A>. So the engine continues with <TT CLASS=syntax>z</TT> which matches the first <tt class=match>z</tt> in the string. Now, the regex engine has reached the end of the regex. But since it鈥檚 two levels deep in recursion, it hasn鈥檛 found an overall match yet. It only has found a match for <TT CLASS=syntax>(?R)</TT>. Exiting the recursion after a successful match, the engine also reaches <TT CLASS=syntax>z</TT>. It now matches the second <tt class=match>z</tt> in the string. The engine is still one level deep in recursion, from which it exits with a successful match. Finally, <TT CLASS=syntax>z</TT> matches the third <tt class=match>z</tt> in the string. The engine is again at the end of the regex. This time, it鈥檚 not inside any recursion. Thus, it returns <tt class=match>aaazzz</tt> as the overall regex match. <a name="balanced"></a><h2>Matching Balanced Constructs</h2> The main purpose of recursion is to match balanced constructs or nested constructs. The generic regex is <TT CLASS=syntax>b(?:m|(?R))*e</TT> where <TT CLASS=syntax>b</TT> is what begins the construct, <TT CLASS=syntax>m</TT> is what can occur in the middle of the construct, and <TT CLASS=syntax>e</TT> is what can occur at the end of the construct. For correct results, no two of <TT CLASS=syntax>b</TT>, <TT CLASS=syntax>m</TT>, and <TT CLASS=syntax>e</TT> should be able to match the same text. You can use an <A HREF="atomic.html" TARGET="_top">atomic group</A> instead of the <A HREF="brackets.html" TARGET="_top">non-capturing group</A> for improved performance: <TT CLASS=syntax>b(?>m|(?R))*e</TT>. A common real-world use is to match a balanced set of parentheses. <TT CLASS=syntax>\((?>[^()]|(?R))*\)</TT> matches a single pair of parentheses with any text in between, including an unlimited number of parentheses, as long as they are all properly paired. If the subject string contains unbalanced parentheses, then the first regex match is the leftmost pair of balanced parentheses, which may occur after unbalanced opening parentheses. If you want a regex that does not find any matches in a string that contains unbalanced parentheses, then you need to use a <A HREF="subroutine.html" TARGET="_top">subroutine call</A> instead of recursion. If you want to find a sequence of multiple pairs of balanced parentheses as a single match, then you also need a subroutine call. <h2>Recursion with Alternation</h2> If what may appear in the middle of the balanced construct may also appear on its own without the beginning and ending parts then the generic regex is <TT CLASS=syntax>b(?R)*e|m</TT>. Again, <TT CLASS=syntax>b</TT>, <TT CLASS=syntax>m</TT>, and <TT CLASS=syntax>e</TT> all need to be mutually exclusive. <TT CLASS=syntax>\((?R)*\)|[^()]+</TT> matches a pair of balanced parentheses like the regex in the previous section. But it also matches any text that does not contain any parentheses at all. This regular expression does not work correctly in Boost. If a regex has <A HREF="alternation.html" TARGET="_top">alternation</A> that is not inside a group then recursion of the whole regex in Boost only attempts the first alternative. So <TT CLASS=syntax>\((?R)*\)|[^()]+</TT> in Boost matches any number of balanced parentheses nested arbitrarily deep with no text in between, or any text that does not contain any parentheses at all. If you flip the alternatives then <TT CLASS=syntax>[^()]+|\((?R)*\)</TT> in Boost matches any text without any parentheses or a single pair of parentheses with any text without parentheses in between. In all other flavors these two regexes find the same matches. The solution for Boost is to put the alternation inside a group. <TT CLASS=syntax>(?:\((?R)*\)|[^()]+)</TT> and <TT CLASS=syntax>(?:[^()]+|\((?R)*\))</TT> find the same matches in all flavors discussed in this tutorial that support recursion.<div id=cntmobi>|&ensp;<a href='quickstart.html'>Quick Start</a>&ensp;|&ensp;<a href='tutorial.html'>Tutorial</a>&ensp;|&ensp;<a href='tools.html'>Tools & Languages</a>&ensp;|&ensp;<a href='examples.html'>Examples</a>&ensp;|&ensp;<a href='refflavors.html'>Reference</a>&ensp;|&ensp;<a href='books.html'>Book Reviews</a>&ensp;||&ensp;<a href='tutorial.html'>Introduction</a>&ensp;|&ensp;<a href='tutorialcnt.html'>Table of Contents</a>&ensp;|&ensp;<a href='characters.html'>Special Characters</a>&ensp;|&ensp;<a href='nonprint.html'>Non-Printable Characters</a>&ensp;|&ensp;<a href='engine.html'>Regex Engine Internals</a>&ensp;|&ensp;<a href='charclass.html'>Character Classes</a>&ensp;|&ensp;<a href='charclasssubtract.html'>Character Class Subtraction</a>&ensp;|&ensp;<a href='charclassintersect.html'>Character Class Intersection</a>&ensp;|&ensp;<a href='shorthand.html'>Shorthand Character Classes</a>&ensp;|&ensp;<a href='dot.html'>Dot</a>&ensp;|&ensp;<a href='anchors.html'>Anchors</a>&ensp;|&ensp;<a href='wordboundaries.html'>Word Boundaries</a>&ensp;|&ensp;<a href='alternation.html'>Alternation</a>&ensp;|&ensp;<a href='optional.html'>Optional Items</a>&ensp;|&ensp;<a href='repeat.html'>Repetition</a>&ensp;|&ensp;<a href='brackets.html'>Grouping & Capturing</a>&ensp;|&ensp;<a href='backref.html'>Backreferences</a>&ensp;|&ensp;<a href='backref2.html'>Backreferences, part 2</a>&ensp;|&ensp;<a href='named.html'>Named Groups</a>&ensp;|&ensp;<a href='backrefrel.html'>Relative Backreferences</a>&ensp;|&ensp;<a href='branchreset.html'>Branch Reset Groups</a>&ensp;|&ensp;<a href='freespacing.html'>Free-Spacing & Comments</a>&ensp;|&ensp;<a href='unicode.html'>Unicode</a>&ensp;|&ensp;<a href='modifiers.html'>Mode Modifiers</a>&ensp;|&ensp;<a href='atomic.html'>Atomic Grouping</a>&ensp;|&ensp;<a href='possessive.html'>Possessive Quantifiers</a>&ensp;|&ensp;<a href='lookaround.html'>Lookahead & Lookbehind</a>&ensp;|&ensp;<a href='lookaround2.html'>Lookaround, part 2</a>&ensp;|&ensp;<a href='keep.html'>Keep Text out of The Match</a>&ensp;|&ensp;<a href='conditional.html'>Conditionals</a>&ensp;|&ensp;<a href='balancing.html'>Balancing Groups</a>&ensp;|&ensp;<a href='recurse.html'>Recursion</a>&ensp;|&ensp;<a href='subroutine.html'>Subroutines</a>&ensp;|&ensp;<a href='recurseinfinite.html'>Infinite Recursion</a>&ensp;|&ensp;<a href='recurserepeat.html'>Recursion & Quantifiers</a>&ensp;|&ensp;<a href='recursecapture.html'>Recursion & Capturing</a>&ensp;|&ensp;<a href='recursebackref.html'>Recursion & Backreferences</a>&ensp;|&ensp;<a href='recursebacktrack.html'>Recursion & Backtracking</a>&ensp;|&ensp;<a href='posixbrackets.html'>POSIX Bracket Expressions</a>&ensp;|&ensp;<a href='zerolength.html'>Zero-Length Matches</a>&ensp;|&ensp;<a href='continue.html'>Continuing Matches</a>&ensp;|</div> <div id=copyright> Page URL: <A HREF="https://www.regular-expressions.info/recurse.html" TARGET="_top">https://www.regular-expressions.info/recurse.html</A> Page last updated: 22 November 2019 Site last updated: 06 November 2024 Copyright © 2003-2024 Jan Goyvaerts. All rights reserved. </div> </div> </div> </body></html>