一般来说，递归的正则表达式用来匹配任意嵌套层次的结构或左右对称的结构。例如匹配：

((((()))))
(hello (world) good (boy) bye)
<p>hello world <strong>hello world</strong> </p>
abc.def.ghij...stu.vwx.yz
abcdcba
123454321

递归正则在正则表达式里算是比较灵活的部分，换句话说就是可能会比较难。下面这个正则表达式是在网上流传的非常广泛的递归正则的示例，它用来匹配嵌套任意次数的括号，括号内可以有其它字符，比如可以匹配(a(bc)de)、(abc(bc(def)c)de)。

# 使用了x修饰符，忽略正则表达式内的空白符号
/\( ( (?>[^()]+) | (\g<0>) )* \)/x

这似乎看不怎么懂？其实即使知道了正则递归的方式，也还是很难看懂(至少，我分析了很久)。

难懂的原因大概是因为这里使用的固化分组在多选分支|中属于一个技巧性的写法，而且分组外还使用了量词*，这些结合起来就太难懂了。

正因为网上到处流传这个例子，曾使我多次对递归正则的学习望而却步。这里我也不去解释这个递归正则的含义，因为"太学术化"或者说"太装xyx逼"，而一般递归正则完全可以写的很简单但却能实现目标。

如何写出简单易懂版本的递归正则并且理解递归正则的匹配方式，正是本文的目标。在后文，我介绍了一个更加简单、更加容易理解的版本，同样能实现这个递归匹配的需求。

为了解释清楚递归正则，本文会以循序渐进的方式逐步深入到递归正则的方方面面。所以，篇幅可能稍大，其中大量篇幅都用在了解释分析递归正则是如何递归匹配上。

注：
本文以Ruby的正则表达式来介绍递归正则，但对其它支持递归正则的语言也是能通用的。例如Perl、PHP、Python(自带的re不提供，但第三方库regex提供递归正则)等。

理解反向引用\N和\g

首先通过正则表达式的反向引用的用法来逐步引入递归正则表达式的用法。

正则表达式(abc|def) and \1xyz可以匹配字符串"abc and abcxyz"或"def and defxyz"，但是不能匹配"abc and defxyz"或def and abcxyz。这是因为，反向引用在引用的时候，只能引用之前分组捕获成功后的那个结果。

reg = /(abc|def) and \1xyz/

reg =~ "abc and abcxyz"  #=>0
reg =~ "def and defxyz"  #=>0
reg =~ "def and abcxyz"  #=>nil
reg =~ "abc and defxyz"  #=>nil

但是，如果使用\g<1>来代替\1，那么就能匹配这四种情形的字符串(Perl中使用(?1)对应这里的\g<1>)：

reg = /(abc|def) and \g<1>xyz/

reg =~ "abc and abcxyz"  #=>0
reg =~ "def and defxyz"  #=>0
reg =~ "def and abcxyz"  #=>0
reg =~ "abc and defxyz"  #=>0

\g<1>和\1的区别在于：\1在反向引用的时候，引用的是该分组捕获到的结果值，\g<1>则不是反向引用，而是直接将索引号为1的分组捕获重新执行捕获分组的匹配操作。相当于是/(abc|def) and (abc|def)xyz/。

所以，\1相当于是在引用的位置插入索引号为1的分组捕获的结果，\g<1>相当于是在此处插入索引号为1的分组捕获表达式，让其能再次进行分组表达式这部分的匹配操作。

如果把分组捕获表达式看作是函数的定义，那么开始匹配时表示调用该函数进行分组捕获。而反向引用\N则是在引用位置处插入该函数的返回值，\g<name>则表示在此处再次调用该函数进行匹配。

\g<name>的name可以是数值型的分组索引号，也可以是命名捕获的名称索引，还可以是0表示整个正则表达式自身。

/(abc|def) and \g<1>xyz/
/(?<var>abc|def) and \g<var>xyz/
/(abc|def) and \g<0>xyz/  # 错误正则，稍后分析

=begin
# Perl、Python(regex，非re)、PHP与之对应的方式：
\g<0>    -> (?R)或(?0)
\g<N>    -> (?N)
\g<name> -> (?P>name)或(?&name)
=end

前面两种好理解，第三种使用\g<0>就不太能理解了，继续向下看。

初探递归正则：递归正则匹配什么

\g<0>表示正则表达式自身，所以这相当于是递归正则表达式，假如进行第一轮正则表达式替换的话，相当于：

/(abc|def) and (abc|def) and \g<0>xyzxyz/

当然，这里只是为了帮助理解才将\g<0>替换成正则表达式，但它不会真的直接替换正则表达式的定义。就像函数调用时，不会在调用函数的地方替换成函数定义里的代码再去执行，函数定义了就能多次复用。

不管怎样，不难发现这里已经出现了无限递归的可能性，因为替换一轮后的正则表达式中再次包含了\g<0>，它可以再次进行第二轮替换、第三轮替换......

那么，对于/(abc|def) and \g<0>xyz/这个递归的正则表达式来说，它能匹配什么样的字符串呢？这才是理解正则递归时最需要关心的。

可以将上面的\g<0>看作是一个占位符，首先它可以匹配"abc and _xyz"或者def and _xyz这种格式的字符串，这里我用了_表示\g<0>占位符。递归一轮的话，它可以匹配"abc and def and _xyzxyz"，这里又会继续递归下去，将没完没了。所以这里先将该正则匹配什么字符串的问题保留，稍后再回头分析。

事实上，/(abc|def) and \g<0>xyz/是错误的正则表达式，它会提示我们，递归没有终点：

/(abc|def) and \g<0>xyz/
#=>SyntaxError: never ending recursion

所以，使用递归正则必须要保证递归能够有终点。

保证正则递归的终点

怎么保证递归正则的终点呢？只要给\g<>这部分做一个量词的限定即可，比如：

\g<0>+        # 错误正则
\g<0>{3}      # 错误正则
\g<0>{,3}     # 错误正则

\g<0>*        # 正确正则
\g<