Recursive Macros

A recursive macro is a macro_rules! macro that invokes itself in its expansion body to process input tokens step by step. Combined with internal @rule prefixes and Incremental TT Munchers, recursive macros enable stateful compile-time parsing of domain-specific languages (DSLs) that cannot be expressed with a single flat $()* repetition.

Pattern 1: Incremental Token-Tree (TT) Muncher

An Incremental TT Muncher matches and processes one command or statement from the front of the input token stream ($head:tt or a structured prefix), and passes the remaining tail $($rest:tt)* recursively to itself until the empty base case () is reached:

TT Muncher Execution Trace:
  state_machine!( init -> running; running -> stopped; )
    |
    +-- Step 1: Processes `init -> running;`, recurses on `running -> stopped;`
    +-- Step 2: Processes `running -> stopped;`, recurses on `` (empty)
    +-- Step 3: Matches base case `()` -> Terminates!

Pattern 2: Internal @ Rules and Push-Down Accumulators

To hide intermediate recursive helper states from external callers (and avoid polluting the module namespace with extra helper macros), prefix internal helper arms with @step_name:

macro_rules! reversed_vec {
    // Internal base case: when no input items remain, construct the Vec from
    // the accumulated `$acc` items:
    (@rev [ $($acc:expr),* ] ) => {
        vec![ $($acc),* ]
    };

    // Internal recursive step: pop `$head` from the front of the remaining inputs
    // and push it onto the FRONT of the accumulator `[ $head $(, $acc)* ]`:
    (@rev [ $($acc:expr),* ] $head:expr $(, $tail:expr)* ) => {
        reversed_vec!(@rev [ $head $(, $acc)* ] $($tail),*)
    };

    // Public entry point: initializes empty accumulator `@rev []`:
    ( $( $item:expr ),* $(,)? ) => {
        reversed_vec!(@rev [] $($item),*)
    };
}

fn main() {
    let rev = reversed_vec![10, 20, 30, 40];
    println!("reversed_vec: {:?}", rev);
}

reversed_vec: [40, 30, 20, 10]

Avoiding Quadratic Compile-Time Blowup in Recursive Macros

Every recursive step of a TT muncher copies the entire remaining $($tail:tt)* token stream. If a TT muncher processes $N$ items one by one, it copies $N + (N - 1) + \dots + 1 = O(N^2)$ tokens!

Whenever possible:

1. Prefer flat $( ... )* repetitions over recursion (repetitions run in $O(N)$ linear time).
2. If recursion is only needed to handle heterogeneous statement kinds, emit each statement as a standalone macro call inside a flat block { $( process_one!($stmt); )* } so each item expands in $O(1)$ depth without copying the tail!