Recursive Descent Parsing & Heuristic Search

The gap this subtopic closes

Every backtracking problem so far generates candidates over a fixed, finite structure — subsets of a set, orderings of a set, placements on a board. This subtopic covers two different applications of the same recursive-exploration instinct: using recursion to parse structured text (where the "candidates" are ways to group characters into a grammar, and mutual recursion — introduced in the Foundations recursion subtopic — is the natural shape), and heuristic search, where the search space is too large to backtrack through exhaustively and you deliberately give up completeness in exchange for tractability. It also covers a genuinely dangerous failure mode — catastrophic backtracking in regex engines — that has caused real production outages.

Recursive descent parsing: mutual recursion, applied

The idea. A recursive descent parser is a direct translation of a grammar into code: one function per grammar rule, where each function's job is "consume the input that matches my rule, calling other rule-functions for the pieces that are themselves sub-expressions." This is the mutual-recursion shape flagged (but not elaborated on) in the Foundations recursion subtopic — parse_expression calls parse_term, which calls parse_factor, which calls back into parse_expression for anything inside parentheses.

Worked example: an arithmetic expression evaluator with + - * / and parentheses. The grammar, from lowest to highest precedence:

expression := term (('+' | '-') term)*
term       := factor (('*' | '/') factor)*
factor     := NUMBER | '(' expression ')'

Each precedence level gets its own function, and lower-precedence operators are handled at the outer level — this is precisely what makes 2 + 3 * 4 parse as 2 + (3 * 4) without an explicit precedence table: parse_expression only ever sees the result of a fully-reduced term, so multiplication has already happened by the time addition looks at it.

class Parser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0

    def peek(self):
        return self.tokens[self.pos] if self.pos < len(self.tokens) else None

    def consume(self):
        tok = self.tokens[self.pos]
        self.pos += 1
        return tok

    def parse_expression(self):
        value = self.parse_term()
        while self.peek() in ("+", "-"):
            op = self.consume()
            rhs = self.parse_term()
            value = value + rhs if op == "+" else value - rhs
        return value

    def parse_term(self):
        value = self.parse_factor()
        while self.peek() in ("*", "/"):
            op = self.consume()
            rhs = self.parse_factor()
            value = value * rhs if op == "*" else value // rhs
        return value

    def parse_factor(self):
        if self.peek() == "(":
            self.consume()               # '('
            value = self.parse_expression()  # recurse back to the top level
            self.consume()               # ')'
            return value
        return self.consume()            # NUMBER

This is the same skeleton behind real interpreters, calculators, and the expression-parsing stage of most compilers. Basic Calculator and Basic Calculator II (which you likely already solved with an explicit stack in the Stack topic) are the exact same problem — the stack-based solution there is the iterative translation of the mutually-recursive structure above, in the same way the Foundations subtopic showed converting recursion to an explicit stack generally. Seeing both solutions side by side is worth the five minutes: the stack tracks "what am I in the middle of" exactly where the recursive version relies on the call stack to remember it implicitly. Basic Calculator III adds parentheses back on top of full operator precedence, forcing the two approaches to combine — a natural next problem once both individual pieces feel solid.

A minimal regex engine, and why some regexes can take down a service

The core idea. A regex matcher for a minimal grammar (literal characters, . for "any character," * for "zero or more of the preceding element") is itself a small backtracking search: try matching the pattern against the string one piece at a time, and when * gives you a choice (match zero more, or match one more and recurse), try one option and backtrack to the other if it doesn't lead to a full match.

def is_match(text: str, pattern: str) -> bool:
    if not pattern:
        return not text

    first_matches = bool(text) and (pattern[0] == text[0] or pattern[0] == ".")

    if len(pattern) >= 2 and pattern[1] == "*":
        # Option A: skip the 'x*' entirely (zero occurrences).
        # Option B: consume one character and try 'x*' again (one more occurrence).
        return is_match(text, pattern[2:]) or (
            first_matches and is_match(text[1:], pattern)
        )

    return first_matches and is_match(text[1:], pattern[1:])

Regular Expression Matching and Wildcard Matching (LeetCode's ./* and ?/* variants, respectively) are exactly this algorithm — and both are frequently taught as Dynamic Programming problems, because the naive recursion above recomputes overlapping (text_position, pattern_position) subproblems repeatedly, exactly the memoization opportunity from the Foundations recursion subtopic's Fibonacci example. Recognizing "this is backtracking with overlapping subproblems, so I should memoize on (i, j)" is the bridge between this topic and Dynamic Programming's top-down approach — the same bridge you'll cross constantly once you reach that topic.

Catastrophic backtracking (ReDoS). The naive backtracking matcher above has a serious failure mode: certain patterns combined with certain inputs cause the number of backtracking branches explored to explode exponentially. The classic trigger is nested or adjacent quantifiers with overlapping matches — a pattern like (a+)+$ against a string like "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!" (many as followed by a character that breaks the match): the engine tries every possible way of partitioning the as among the repetitions of (a+), discovers at the very end that none of them work (because of the trailing !), and the number of partitions to try grows exponentially with the string length. This is a real, named vulnerability class — ReDoS (Regular Expression Denial of Service) — and it has caused genuine production outages: a catastrophically-backtracking regex in a WAF rule caused a widely-reported multi-hour global outage at a major CDN/security provider in 2019, because a single request matching the pathological pattern pegged CPU across their edge network. The fix in production regex engines is either (a) impose a step/time budget and bail out, or (b) use an automaton-based matching engine (Thompson's construction, compiling the regex to an NFA/DFA and simulating all possible states in parallel) that guarantees O(n·m) time with no backtracking at all — Google's RE2 library and Rust's regex crate are both built this way specifically to make ReDoS structurally impossible, at the cost of not supporting a few backtracking-dependent regex features (backreferences, in particular).

Beam search: heuristic search when even backtracking-with-pruning is too slow

Every backtracking algorithm in this topic so far still guarantees finding a correct answer if one exists — pruning skips provably dead branches, but it's exhaustive over everything else. Beam search gives that guarantee up on purpose: at each level of the search tree, expand every current candidate one step, score all the resulting candidates with a heuristic, and keep only the top-k ("beam width" k) — discarding the rest permanently, even if one of them might have led to the true optimum.

def beam_search(start, expand, score, beam_width, is_goal):
    beam = [start]
    while beam and not any(is_goal(c) for c in beam):
        candidates = [next_c for c in beam for next_c in expand(c)]
        if not candidates:
            break
        candidates.sort(key=score, reverse=True)
        beam = candidates[:beam_width]  # keep only the top k, discard the rest permanently
    return beam

This trades optimality for tractability in a search space too large for even a well-pruned backtracking search to finish — the beam width k is a direct, tunable dial between speed (small k) and solution quality (large k; k = infinity recovers exhaustive breadth-first search). Where it's actually used: beam search is the standard decoding strategy in machine translation and speech recognition (at each output position, keep the top-k most likely partial sentences instead of exploring every possible continuation) and in modern LLM text generation (the same idea — greedy decoding is beam width 1; sampling-based decoding is a different tradeoff, but beam search remains the default for tasks wanting the single most-likely, rather than most-diverse, output sequence).

Comparison: exhaustive backtracking vs. beam search

	Exhaustive backtracking (N-Queens, Sudoku)	Beam search
Guarantee	Finds the/a correct solution if one exists	No guarantee — may discard the branch containing the true optimum
Pruning	Only provably-dead branches are cut	Actively discards live (possibly-good) branches to bound width
When to use	Search space is small enough, or pruning is strong enough, to finish in time	Search space is too large for any amount of correct pruning to help

Complexity summary

Technique	Time	Space	Notes
Recursive descent parsing	O(n)	O(d) (d = nesting depth, for the call stack)	One pass, assuming no backtracking within the grammar itself
Naive backtracking regex match	O(2ⁿ) worst case	O(n) recursion depth	Exponential on adversarial nested-quantifier patterns (ReDoS)
Regex match, memoized (DP)	O(n·m)	O(n·m)	n, m = text and pattern length; the fix for the above
Automaton-based regex (RE2-style)	O(n·m), no backtracking	O(m) (state set size)	Structurally immune to ReDoS; drops backreference support
Beam search	O(depth · k · branching factor)	O(k)	k = beam width; tunable speed/quality tradeoff

Pitfalls and interview gotchas

Writing a backtracking regex/wildcard matcher without noticing the overlapping-subproblems opportunity. If asked to optimize, memoizing on (text_index, pattern_index) is the very next step — flag this explicitly rather than waiting to be asked.
Not knowing ReDoS by name. If you're asked "what could go wrong with a hand-rolled backtracking regex matcher on untrusted input," naming catastrophic backtracking / ReDoS and the nested-quantifier trigger pattern is the answer the question is fishing for.
Treating beam search as "just backtracking with a smaller k." The critical difference is that beam search's pruning is not safe — it can and does discard the actual optimal path. Say this out loud if asked to compare the two; conflating them signals a shallow understanding of the tradeoff.
Recursive descent parser: forgetting that lower-precedence operators must live in the outer function. Swap the nesting (put *// in the outer function, +/- in the inner one) and precedence silently inverts — trace a small multi-operator example by hand before trusting the structure.

How to talk about this in an interview

"I'll write this as a recursive descent parser: one function per precedence level, with lower-precedence operators in the outer function so they naturally combine already-reduced higher-precedence sub-results. Parentheses just recurse back to the top-level function. This is the same shape as Basic Calculator, which I solved with an explicit stack — the stack there is standing in for what the call stack does automatically here."

"A naive backtracking regex matcher can blow up exponentially on adversarial input with nested quantifiers — that's the ReDoS vulnerability class, and it's caused real production outages. I'd either memoize on (text position, pattern position) to make it polynomial, or, for untrusted input in production, use an automaton-based engine like RE2 that structurally can't backtrack at all."

Further Resources (Optional)

Practice Problems

Interview relevancy:!!!Critical — must-have!!Important — highly recommended!Good to have~Niche — rarely asked

Basic Calculator IIIHardPremiumFree replacement!4/540m
Regular Expression MatchingHard!5/545m

Optional Practice (Extra Reps)

For once you've cleared the main set above and want more reps on this pattern. These don't count toward the roadmap's progress stats — solve them purely for your own benefit.

Wildcard MatchingHard!5/545m
Expression Add OperatorsHard~5/545m