Recursive pattern matching in C Sharp (C#) - Deep Dive

Overview - Recursive pattern matching

What is it?

Recursive pattern matching is a way to check if a complex data structure fits a certain shape by looking inside it step-by-step. It lets you test nested parts of an object or value by breaking it down into smaller pieces and matching each piece. This helps write clear and concise code that handles many cases in a simple way. It is often used with objects that have properties or with data like trees or lists.

Why it matters

Without recursive pattern matching, checking complex nested data would require many manual steps and lots of code, making programs harder to read and maintain. Recursive pattern matching solves this by letting you describe the shape you want to find in a clear, natural way. This reduces bugs and makes your code easier to understand and change. It also helps when working with data that has many layers, like JSON or tree structures.

Where it fits

Before learning recursive pattern matching, you should understand basic pattern matching and object properties in C#. After mastering it, you can explore advanced topics like switch expressions, records, and functional programming styles in C#.

Mental Model

Core Idea

Recursive pattern matching breaks down complex data step-by-step, matching each nested part to a pattern until the whole structure fits or fails.

Think of it like...

It's like opening nested boxes inside boxes, checking each box's label to see if it matches what you expect, and only if all boxes match, you accept the whole set.

Data Structure
  ├─ Outer Object
  │    ├─ Property A (matches pattern)
  │    └─ Property B (nested object)
  │          ├─ Subproperty 1 (matches)
  │          └─ Subproperty 2 (matches)
  └─ Result: Match if all parts match

Build-Up - 7 Steps

1

Foundation

Basic pattern matching in C#

Concept: Introduces simple pattern matching with types and constants.

In C#, you can check if a value matches a type or constant using the 'is' keyword. Example: int x = 5; if (x is 5) { Console.WriteLine("x is five"); } if (x is int number) { Console.WriteLine($"x is an int: {number}"); }

Result

The program prints 'x is five' and 'x is an int: 5'.

Understanding simple pattern matching is the foundation for recognizing how to check values and extract data in one step.

2

Foundation

Matching object properties

Concept: Shows how to match an object and check its properties in one pattern.

You can match an object and its properties using property patterns. Example: class Point { public int X { get; } public int Y { get; } public Point(int x, int y) { X = x; Y = y; } } Point p = new Point(3, 4); if (p is Point { X: 3, Y: 4 }) { Console.WriteLine("Point at (3,4)"); }

Result

The program prints 'Point at (3,4)'.

Matching properties lets you check multiple parts of an object at once, making code clearer and more concise.

3

Intermediate

Introducing recursive patterns

🤔Before reading on: do you think you can match nested objects by repeating property patterns inside each other? Commit to yes or no.

Concept: Explains how to match nested objects by applying patterns inside property patterns recursively.

If an object has properties that are themselves objects, you can match those inner objects using nested property patterns. Example: class Rectangle { public Point TopLeft { get; } public Point BottomRight { get; } public Rectangle(Point tl, Point br) { TopLeft = tl; BottomRight = br; } } Rectangle r = new Rectangle(new Point(0, 0), new Point(5, 5)); if (r is Rectangle { TopLeft: { X: 0, Y: 0 }, BottomRight: { X: 5, Y: 5 } }) { Console.WriteLine("Rectangle from (0,0) to (5,5)"); }

Result

The program prints 'Rectangle from (0,0) to (5,5)'.

Recognizing that patterns can be nested inside each other unlocks the power to match deeply nested data structures naturally.

4

Intermediate

Using recursive patterns with lists

🤔Before reading on: do you think recursive pattern matching can be used to check elements inside a list one by one? Commit to yes or no.

Concept: Shows how to match elements inside collections recursively using patterns like list patterns.

C# supports list patterns to match elements inside arrays or lists. Example: int[] numbers = {1, 2, 3}; if (numbers is [1, 2, 3]) { Console.WriteLine("Matched exact list"); } // Recursive matching example: if (numbers is [1, .. var rest]) { Console.WriteLine($"Starts with 1, rest length {rest.Length}"); }

Result

The program prints 'Matched exact list' and 'Starts with 1, rest length 2'.

Knowing that recursive patterns work with collections lets you handle sequences and nested data flexibly.

5

Advanced

Combining recursive patterns with switch expressions

🤔Before reading on: do you think switch expressions can use recursive patterns to simplify complex conditional logic? Commit to yes or no.

Concept: Demonstrates how to use recursive patterns inside switch expressions for clean, readable branching on nested data.

Switch expressions let you match patterns and return values concisely. Example: string DescribeShape(object shape) => shape switch { Rectangle { TopLeft: { X: 0, Y: 0 }, BottomRight: { X: var x, Y: var y } } => $"Rectangle size {x}x{y}", Point { X: var x, Y: var y } => $"Point at ({x},{y})", _ => "Unknown shape" }; Console.WriteLine(DescribeShape(new Rectangle(new Point(0,0), new Point(5,5))));

Result

The program prints 'Rectangle size 5x5'.

Combining recursive patterns with switch expressions creates very readable code that handles many nested cases elegantly.

6

Advanced

Recursive pattern matching with records

Concept: Shows how records simplify recursive pattern matching by providing built-in deconstruction.

Records automatically support deconstruction, making recursive patterns easier. Example: record Point(int X, int Y); record Rectangle(Point TopLeft, Point BottomRight); Rectangle r = new(new Point(0, 0), new Point(5, 5)); if (r is Rectangle(Point(0, 0), Point(var x, var y))) { Console.WriteLine($"Rectangle size {x}x{y}"); }

Result

The program prints 'Rectangle size 5x5'.

Understanding that records simplify recursive pattern matching reduces boilerplate and improves clarity.

7

Expert

Performance and pitfalls of recursive patterns

🤔Before reading on: do you think recursive pattern matching always runs fast and never causes stack issues? Commit to yes or no.

Concept: Explores how recursive pattern matching compiles and its performance implications, including risks of deep recursion.

Recursive patterns compile into nested if-checks and property accesses. Deeply nested data can cause many calls and checks, impacting performance. Beware of very deep recursion causing stack overflow or slowdowns. Example: Matching a deeply nested tree structure with many levels may be costly. Optimizations include flattening data or limiting recursion depth.

Result

Understanding this helps write efficient code and avoid runtime errors.

Knowing the internal cost of recursive patterns prevents performance bugs and guides better data design.

Under the Hood

Recursive pattern matching works by the compiler generating code that checks each pattern part step-by-step. For nested patterns, it generates nested if-statements or calls that check inner properties or elements. When a pattern matches, it extracts values into variables if specified. This process continues recursively until the whole pattern is matched or a mismatch is found. The runtime evaluates these checks in order, short-circuiting on failure.

Why designed this way?

This design allows expressive, readable code that looks like describing data shapes directly. It avoids manual code to check each property or element. The recursive approach fits naturally with nested data structures common in programming. Alternatives like manual checks are verbose and error-prone. The pattern matching syntax was introduced in C# 7 and improved in later versions to support recursion and more complex patterns.

┌─────────────────────────────┐
│ Input Data (object/structure)│
└─────────────┬───────────────┘
              │
      ┌───────▼────────┐
      │ Pattern Matcher │
      └───────┬────────┘
              │
  ┌───────────▼────────────┐
  │ Check outer pattern     │
  │ ┌────────────────────┐ │
  │ │ Check nested parts  │ │
  │ │ ┌───────────────┐  │ │
  │ │ │ Recursive call │  │ │
  │ │ └───────────────┘  │ │
  │ └────────────────────┘ │
  └───────────┬────────────┘
              │
      ┌───────▼────────┐
      │ Match or Fail  │
      └────────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does recursive pattern matching automatically handle null values inside nested objects? Commit to yes or no.

Common Belief: Recursive pattern matching always safely handles null nested properties without extra checks.

Reality: If a nested property is null, the pattern match fails unless you explicitly handle null cases in the pattern.

Why it matters: Ignoring nulls can cause unexpected match failures or runtime exceptions, leading to bugs in real programs.

Quick: Can recursive pattern matching modify the matched object? Commit to yes or no.

Common Belief: Pattern matching can change the data it matches against.

Reality: Pattern matching only reads and tests data; it never modifies the original object or value.

Why it matters: Expecting side effects from pattern matching leads to incorrect assumptions about program behavior.

Quick: Does recursive pattern matching always improve performance compared to manual checks? Commit to yes or no.

Common Belief: Using recursive pattern matching is always faster than writing manual if-else checks.

Reality: Recursive pattern matching can be less efficient in some cases due to overhead of nested checks and allocations.

Why it matters: Blindly using recursive patterns without considering performance can cause slowdowns in critical code.

Quick: Is recursive pattern matching only useful for objects with properties? Commit to yes or no.

Common Belief: Recursive pattern matching only works with objects that have named properties.

Reality: It also works with tuples, records, lists, and other data structures that support deconstruction or indexing.

Why it matters: Limiting understanding to objects misses many powerful use cases in functional and data-driven programming.

Expert Zone

1

Recursive pattern matching can be combined with positional patterns and property patterns for maximum expressiveness.

2

Compiler optimizations may inline simple recursive patterns, but complex deep patterns can generate verbose code.

3

Patterns can be combined with 'when' clauses to add extra conditions, increasing flexibility but also complexity.

When NOT to use

Avoid recursive pattern matching when performance is critical and data is deeply nested or very large; manual optimized checks or specialized parsers may be better. Also, if data structures are irregular or incomplete, pattern matching may become cumbersome. Alternatives include visitor patterns or explicit traversal methods.

Production Patterns

In production, recursive pattern matching is used for parsing JSON or XML data, handling abstract syntax trees in compilers, and processing nested UI components. It is often combined with switch expressions and records to write concise, maintainable code that clearly expresses intent.

Connections

Functional programming recursion

Recursive pattern matching builds on the idea of breaking problems into smaller parts recursively.

Understanding recursion in functional programming helps grasp how recursive patterns naturally decompose nested data.

Tree data structures

Recursive pattern matching is a natural fit for traversing and matching tree-like nested data.

Knowing tree traversal algorithms clarifies how recursive patterns navigate nested objects step-by-step.

Linguistics phrase structure parsing

Both recursively analyze nested structures to find patterns and meanings.

Seeing recursive pattern matching like parsing sentences helps appreciate its power in breaking down complex data into understandable parts.

Common Pitfalls

#1 Not handling null nested properties causes match failures.

Wrong approach:

if (obj is Rectangle { TopLeft: { X: 0, Y: 0 }, BottomRight: { X: var x, Y: var y } }) { /* ... */ } // fails if TopLeft or BottomRight is null

Correct approach:

if (obj is Rectangle { TopLeft: { X: 0, Y: 0 }, BottomRight: { X: var x, Y: var y } } && obj.TopLeft != null && obj.BottomRight != null) { /* ... */ }

Root cause:

Assuming nested properties are never null without explicit checks.

#2 Expecting pattern matching to modify data.

Wrong approach:

if (obj is Point { X: var x }) { x = 10; } // tries to change matched value

Correct approach:

if (obj is Point { X: var x }) { var newPoint = new Point(10, obj.Y); } // create new object instead

Root cause:

Misunderstanding that pattern matching is read-only.

#3 Using recursive patterns on very deep data without performance consideration.

Wrong approach:

Matching a deeply nested tree with hundreds of levels directly in a pattern without optimization.

Correct approach:

Use iterative traversal or limit recursion depth before pattern matching.

Root cause:

Ignoring performance costs of deep recursion in pattern matching.

Key Takeaways

Recursive pattern matching lets you check complex nested data by matching each part step-by-step.

It makes code clearer and reduces manual checks by describing data shapes directly in patterns.

Records and switch expressions in C# enhance recursive pattern matching with concise syntax.

Be careful with null nested properties and performance when using recursive patterns.

Understanding recursion and data structures helps you use recursive pattern matching effectively.