Regex Recursion

2025-12-28

This page explains how to match arbitrarily deep nested parentheses in Perl using a single recursive regex pattern.

You have probably run into the problem where you need to match (something (with nested (parens))) and your regex engine refuses to cooperate. Standard regular expressions are finite automata, which means they cannot count or remember how many levels deep they have gone. They simply do not support recursion.

Perl does support it.

my $nested = qr~\(   ( (?: [^()]+ | \( (?1) \) )* )   \)~x;

That pattern matches arbitrarily deep nested parentheses. One line. No parsing libraries. No state machines. Just regex.

It looks like someone sneezed on a keyboard, so let us walk through it together.

Part 1: THE OUTER SHELL

Strip away the recursion magic and you are left with a simple sandwich pattern.

\(  ...stuff...  \)

A literal open parenthesis, some content in the middle, and a literal close parenthesis.

The outer shell is the easy part. The content in the middle is where the pattern gets interesting.

Part 2: THE CAPTURING GROUP

\(   ( (?: [^()]+ | \( (?1) \) )* )   \)
     ^                            ^
     |                            |
     +------- GROUP 1 ------------+

Those outer parentheses inside the literal  create Group 1. This is the group that handles recursion. Everything that matches inside it gets captured into $1.

For input like (a(b(c)d)e), Group 1 captures a(b(c)d)e.

Notice that it does not include the outermost parens. Those characters are matched by the literal $ and $ at the edges of the pattern.

Part 3: THE CHOICE

Inside Group 1, there is a non-capturing group that offers two alternatives.

(?: [^()]+ | \( (?1) \) )*

The pattern says: match either of these things, zero or more times.

Option A is [^()]+, which matches one or more characters that are not parentheses. Option B is $, followed by (?1), followed by $. That means an open parenthesis, a recursive dive into Group 1, and a close parenthesis.

The regex engine tries Option A first. If it encounters an open parenthesis instead of a regular character, it switches to Option B and dives deeper into the nesting.

Part 4: THE RECURSION

Here is the core mechanism.

(?1)

This instruction means: run Group 1's pattern right here, right now.

It is not a backreference. A backreference would match exactly what Group 1 already captured. This instruction runs the entire Group 1 pattern again from the current position.

When the engine hits (?1), it pushes its current state onto a stack and starts Group 1 over at the new position. When that nested run finishes, it pops back and continues where it left off.

It is essentially function calls inside a regex.

      .--.
     |o_o |
     |:_/ |
    //   \ \
   (|     | )
  /'\_   _/`\
  \___)=(___/

Your brain should feel a little stretched. That reaction is completely normal.

Part 5: WALKING THROUGH IT

Input: (a(b(c)d)e)

Position:  0 1 2 3 4 5 6 7 8 9 10
Character: ( a ( b ( c ) d ) e )

Here is what happens step by step.

STEP    PATTERN     POS   CHAR   ACTION
-----   ---------   ---   ----   -------------------------
1       \(          0     (      Match literal open paren
2       [^()]+      1     a      Match non-paren char
3       \(          2     (      Match nested open
4       (?1)        -     -      RECURSE into Group 1
5       [^()]+      3     b      Match non-paren (in recursion)
6       \(          4     (      Match deeper open
7       (?1)        -     -      RECURSE AGAIN
8       [^()]+      5     c      Match non-paren (deepest)
9       -           -     -      No more parens, return up
10      \)          6     )      Match close (level 2)
11      [^()]+      7     d      Match non-paren (level 1)
12      -           -     -      Return up
13      \)          8     )      Match close (level 1)
14      [^()]+      9     e      Match non-paren (level 0)
15      \)          10    )      Match final close

Three levels deep. The engine handles the nesting automatically.

Part 6: THE STACK

You can think of the process like nested function calls.

LEVEL 0 (outer):
+------------------------------------------+
| \( matches position 0                    |
|                                          |
| GROUP 1 capturing: a(b(c)d)e             |
|   +-- [^()]+ matches: a                  |
|   +-- \( matches: (                      |
|   +-- (?1) RECURSE ----+                 |
|   :                    :                 |
|   +-- \) matches: ) <--+ (returns here)  |
|   +-- [^()]+ matches: e                  |
|                                          |
| \) matches position 10                   |
+------------------------------------------+

LEVEL 1 (first recursion):
+--------------------------------+
| GROUP 1 matching: b(c)d        |
|   +-- [^()]+ matches: b        |
|   +-- \( matches: (            |
|   +-- (?1) RECURSE --+         |
|   :                  :         |
|   +-- \) matches: ) <+ return  |
|   +-- [^()]+ matches: d        |
+--------------------------------+

LEVEL 2 (deepest):
+--------------+
| GROUP 1: c   |
|   +-- [^()]+:|
|       c      |
| (no parens,  |
|  return up)  |
+--------------+

Each (?1) pushes state onto the stack. Each completed match pops back to the previous level.

Part 7: THE FULL PATTERN ANNOTATED

my $nested = qr~
    \(                  # literal opening paren
    (                   # GROUP 1 - this is what recurses
        (?:             # non-capturing group for the choice
            [^()]+      # Option A: non-paren characters
            |           # OR
            \( (?1) \)  # Option B: open, RECURSE, close
        )*              # zero or more times
    )
    \)                  # literal closing paren
~x;

The /x modifier lets us spread the pattern across multiple lines with inline comments. That version is much easier to read than the compressed single-line version.

Part 8: USING IT

#!/usr/bin/env perl

use v5.14;

# ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Pattern for nested parens
# ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

my $nested = qr~
    \(                  # literal opening paren
    (                   # GROUP 1 - the recursing part
        (?:             # non-capturing choice group
            [^()]+      # one or more non-parens
            |           # OR
            \( (?1) \)  # paren, recurse, paren
        )*              # zero or more of either
    )
    \)                  # literal closing paren
~x;

# ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Test it
# ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

my $text = "func(a, calc(b, inner(c)), d)";

if ($text =~ m~$nested~)
{
    say "Matched: $&";    # full match with outer parens
    say "Inside:  $1";    # contents without outer parens
}

Output:

Matched: (a, calc(b, inner(c)), d)
Inside:  a, calc(b, inner(c)), d

Part 9: VARIATIONS

You can adapt the same structure to match curly braces instead.

my $braces = qr~\{   ( (?: [^{}]+ | \{ (?1) \} )* )   \}~x;

You can also match square brackets.

my $brackets = qr~\[   ( (?: [^\[\]]+ | \[ (?1) \] )* )   \]~x;

Finally, you can match HTML-style tags with a simplified pattern.

my $tags = qr~<(\w+)>   ( (?: [^<>]+ | (?0) )* )   </\1>~x;

That last example uses (?0) to recurse the entire pattern, and \1 as a backreference to ensure the closing tag name matches the opening tag name.

THE CATCH

This feature is Perl-specific. PCRE supports it. Python's standard re module does not, though the third-party regex module does. JavaScript does not support it at all.

If you need portability across languages, you will need to write a traditional parser.

If you are working in Perl, you get one line, unlimited depth, and no external libraries. That is exactly the kind of capability that makes people fall in love with the language.

                     .---.
                    /     \
                    \.@-@./
                    /`\_/`\
                   //  _  \\
                  | \     )|_
                 /`\_`>  <_/ \
                 \__/'---'\__/

perl.gg