Course contentsShow
← JavaScript
Lesson 1732 of 2,72336. Regular ExpressionsFree lesson

Catastrophic Backtracking

How nested quantifiers can cause exponential time complexity and hang your program.

What You'll Learn

You'll learn how certain regex patterns with nested or overlapping quantifiers can cause your program to freeze or hang due to exponential time complexity.

The Core Problem

When a regex engine can't find a match, it tries different combinations by backtracking—undoing previous decisions and trying alternatives. With nested quantifiers (like (a+)+ or (a*)*), the number of possible ways to backtrack grows exponentially with input length.

Think of it like trying to open a combination lock where each wrong guess forces you to try every possible variation of previous guesses again. A 10-character string might require hundreds of attempts; a 20-character string could require millions.

How It Happens

// DANGEROUS PATTERN - DO NOT USE ON UNTRUSTED INPUT
const badRegex = /^(a+)+$/;

// This completes instantly
badRegex.test("aaaaaaaaaa"); // true

// This takes a very long time (and eventually fails)
badRegex.test("aaaaaaaaab");

Why does the second one hang? When the regex reaches b, it fails to match. The engine then backtracks through every possible way to group those as: (a)(a)(a)..., (aa)(a)(a)..., (a)(aa)(a)..., etc. With 10 as, there are over 1,000 combinations to try before giving up.

Safe Alternatives

Replace nested quantifiers with simpler patterns:

// Safe version - no nested quantifiers
const safeRegex = /^a+$/;

If you need grouping, make inner groups non-capturing and avoid stacking quantifiers:

const safer = /^(?:a)+$/; // Non-capturing, but still avoid if possible

Key Takeaway: Avoid patterns with nested quantifiers like (a+)+, (a*)*, or (a+)*—they can cause exponential backtracking that hangs your application on even moderately-sized input.