Recursive pattern matching in C Sharp (C#)

Introduction

Recursive pattern matching helps you check complex data step-by-step by breaking it down into smaller parts. It makes your code easier to read and understand when working with nested or linked data.

When you want to check if a linked list contains a certain value by looking at each node one by one.

When you need to process a tree structure by examining each branch and leaf recursively.

When you want to simplify complex conditional checks on nested objects or data structures.

When you want to write clear and concise code that handles different shapes of data in a recursive way.

Syntax

C Sharp (C#)

public class Node<T>
{
    public T Value { get; set; }
    public Node<T>? Next { get; set; }

    public Node(T value, Node<T>? next = null)
    {
        Value = value;
        Next = next;
    }
}

public static bool ContainsValue<T>(Node<T>? node, T target) where T : IEquatable<T>
{
    return node switch
    {
        null => false, // base case: empty list
        { Value: var value, Next: var next } when value.Equals(target) => true, // found value
        { Next: var next } => ContainsValue(next, target), // recursive call
        _ => false
    };
}

The switch expression is used to match the shape of the data recursively.

Null is the base case to stop recursion.

Examples

Checks an empty list, returns false because no nodes exist.

C Sharp (C#)

ContainsValue<int>(null, 5) // returns false

List with one node that matches the target value.

C Sharp (C#)

var singleNode = new Node<int>(10);
ContainsValue(singleNode, 10) // returns true

List with multiple nodes, target found at the end.

C Sharp (C#)

var list = new Node<int>(1, new Node<int>(2, new Node<int>(3)));
ContainsValue(list, 3) // returns true

List with multiple nodes, target not found.

C Sharp (C#)

var list = new Node<int>(1, new Node<int>(2, new Node<int>(3)));
ContainsValue(list, 4) // returns false

Sample Program

This program creates a linked list of integers and uses recursive pattern matching to check if certain values exist in the list. It prints the list before searching and shows the results of the searches.

C Sharp (C#)

using System;

public class Node<T>
{
    public T Value { get; set; }
    public Node<T>? Next { get; set; }

    public Node(T value, Node<T>? next = null)
    {
        Value = value;
        Next = next;
    }
}

public class Program
{
    public static bool ContainsValue<T>(Node<T>? node, T target) where T : IEquatable<T>
    {
        return node switch
        {
            null => false,
            { Value: var value, Next: var next } when value.Equals(target) => true,
            { Next: var next } => ContainsValue(next, target),
            _ => false
        };
    }

    public static void PrintList<T>(Node<T>? node)
    {
        if (node == null)
        {
            Console.WriteLine("List is empty.");
            return;
        }

        Console.Write("List values: ");
        Node<T>? current = node;
        while (current != null)
        {
            Console.Write(current.Value + " ");
            current = current.Next;
        }
        Console.WriteLine();
    }

    public static void Main()
    {
        var list = new Node<int>(5, new Node<int>(10, new Node<int>(15)));

        Console.WriteLine("Before searching:");
        PrintList(list);

        int searchValue1 = 10;
        Console.WriteLine($"Does the list contain {searchValue1}? {ContainsValue(list, searchValue1)}");

        int searchValue2 = 20;
        Console.WriteLine($"Does the list contain {searchValue2}? {ContainsValue(list, searchValue2)}");
    }
}

Important Notes

Time complexity is O(n) because it may check each node once.

Space complexity is O(n) due to recursive calls on the call stack.

Common mistake: forgetting the base case (null) causes infinite recursion.

Use recursive pattern matching when data is naturally recursive, like linked lists or trees. For flat data, simple loops may be better.

Summary

Recursive pattern matching breaks down data step-by-step to check or process it.

It uses a base case to stop recursion and matches data shapes with switch expressions.

This technique is great for linked lists, trees, and nested data structures.