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.

Practice

1. What is the main purpose of recursive pattern matching in C#?

easy

A. To break down complex data structures step-by-step

B. To create loops that run forever

C. To declare variables without types

D. To handle exceptions automatically

Solution

1. Step 1: Understand recursive pattern matching concept

   Recursive pattern matching is used to analyze data by breaking it down into smaller parts recursively.

2. Step 2: Identify the purpose from options

   To break down complex data structures step-by-step correctly states that it breaks down complex data structures step-by-step, which matches the concept.

3. Final Answer:

   To break down complex data structures step-by-step -> Option A

4. Quick Check:

   Recursive pattern matching = step-by-step data breakdown [OK]

Hint: Think: recursive means breaking down data stepwise [OK]

Common Mistakes:

• Confusing recursion with infinite loops
• Thinking it declares variables
• Assuming it handles exceptions

2. Which of the following is the correct syntax to use recursive pattern matching in a C# switch expression?

easy

A. case Node(var value, var next):

B. case Node[value, next]:

C. case Node->(value, next):

D. case Node[value; next]:

Solution

1. Step 1: Recall C# recursive pattern syntax

   In C#, recursive patterns use parentheses with variables inside, like Node(var value, var next).

2. Step 2: Compare options to correct syntax

   case Node(var value, var next): matches the correct syntax. Other options use invalid symbols like brackets or arrows.

3. Final Answer:

   case Node(var value, var next): -> Option A

4. Quick Check:

   Recursive pattern syntax uses parentheses ( ) [OK]

Hint: Look for parentheses with variables inside in case patterns [OK]

Common Mistakes:

• Using square brackets instead of parentheses
• Using arrows or semicolons incorrectly
• Missing 'var' keyword before variables

3. What will be the output of this C# code snippet?

record Node(int Value, Node? Next);
Node list = new(1, new(2, new(3, null)));

string PrintList(Node? node) => node switch
{
    null => "End",
    Node(var v, var n) => $"{v} -> " + PrintList(n)
};

Console.WriteLine(PrintList(list));

medium

A. 1 2 3 End

B. End

C. 1 -> 2 -> 3 -> End

D. 1 -> 2 -> 3

Solution

1. Step 1: Understand the recursive function PrintList

   PrintList prints the current node's value, then calls itself on the next node, until it reaches null and returns "End".

2. Step 2: Trace the output for list nodes 1, 2, 3

   It prints "1 -> " + PrintList(2), then "2 -> " + PrintList(3), then "3 -> " + PrintList(null), which returns "End".

3. Final Answer:

   1 -> 2 -> 3 -> End -> Option C

4. Quick Check:

   Recursive print with null base case = 1 -> 2 -> 3 -> End [OK]

Hint: Follow recursion calls and base case carefully [OK]

Common Mistakes:

• Ignoring the base case output
• Missing arrows in output
• Confusing spaces with arrows

4. Identify the error in this recursive pattern matching code:

record Node(int Value, Node? Next);
string PrintList(Node? node) => node switch
{
    Node(var v, var n) => $"{v} -> " + PrintList(n),
    null => "End"
};

medium

A. Missing semicolon after switch expression

B. No error, code works correctly

C. The pattern 'Node(var v, var n)' is invalid syntax

D. The order of cases should have 'null' before 'Node' to avoid errors

Solution

1. Step 1: Check switch expression order and syntax

   In C#, switch expressions check patterns top to bottom. Here, 'Node' pattern matches non-null nodes, and 'null' matches null nodes. The order is valid.

2. Step 2: Verify syntax correctness

   The pattern syntax and semicolons are correct. No syntax errors exist.

3. Final Answer:

   No error, code works correctly -> Option B

4. Quick Check:

   Pattern order and syntax are valid [OK]

Hint: Null pattern can be last in switch expressions [OK]

Common Mistakes:

• Thinking null must come first
• Assuming missing semicolon error
• Misreading pattern syntax

5. Given a binary tree defined as:

record TreeNode(int Value, TreeNode? Left, TreeNode? Right);

Write a recursive pattern matching expression to calculate the sum of all values in the tree. Which of the following switch expressions correctly implements this?

hard

A. node switch { null => 0, TreeNode(v, l, r) => v + Sum(l) + Sum(r) }

B. node switch { TreeNode(v, l, r) => v + Sum(l) + Sum(r), null => 0 }

C. node switch { null => 0, TreeNode(var v, var l) => v + Sum(l) }

D. node switch { null => 0, TreeNode(var v, var l, var r) => v + Sum(l) + Sum(r) }

Solution

1. Step 1: Understand the tree structure and sum logic

   The tree node has three parts: Value, Left, and Right. The sum should add the current value plus sums of left and right subtrees.

2. Step 2: Check each option for correct pattern and order

   node switch { null => 0, TreeNode(var v, var l, var r) => v + Sum(l) + Sum(r) } correctly matches null first (base case) and then TreeNode with three variables (value, left, right). It sums value + Sum(left) + Sum(right). node switch { TreeNode(v, l, r) => v + Sum(l) + Sum(r), null => 0 } misses 'var' keywords, which is required. node switch { null => 0, TreeNode(v, l, r) => v + Sum(l) + Sum(r) } misses 'var' keywords, which is required. node switch { null => 0, TreeNode(var v, var l) => v + Sum(l) } misses the right subtree.

3. Final Answer:

   node switch { null => 0, TreeNode(var v, var l, var r) => v + Sum(l) + Sum(r) } -> Option D

4. Quick Check:

   Correct pattern with all parts and base case first [OK]

Hint: Include all node parts and base case null first [OK]

Common Mistakes:

• Omitting 'var' in pattern variables
• Missing one subtree in sum
• Placing null case after non-null without care