Recursive pattern matching in C Sharp (C#) - Step-by-Step Execution

Concept Flow - Recursive pattern matching

Start with input data

↓

Match pattern with 'match'

↓

If pattern matches base case

↓

Return base value

↓

Return

↓

Combine result

↓

Return

The function checks the input against patterns. If it matches a base case, it returns a value. Otherwise, it breaks input down and calls itself recursively, combining results.

Execution Sample

C Sharp (C#)

static int Factorial(int n) => n switch
{
  0 => 1,
  _ => n * Factorial(n - 1)
};

Calculates factorial of n using recursive pattern matching.

Execution Table

Step	Input n	Pattern Matched	Action	Return Value
1	3	Default (_)	Calculate 3 * Factorial(2)	Pending
2	2	Default (_)	Calculate 2 * Factorial(1)	Pending
3	1	Default (_)	Calculate 1 * Factorial(0)	Pending
4	0	Base case (0)	Return 1	1
5	1	Return from recursion	1 * 1	1
6	2	Return from recursion	2 * 1	2
7	3	Return from recursion	3 * 2	6

💡 Reached base case n=0, recursion unwinds returning final result 6

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
n	3	3	2	1	0	1	2	3
Return Value	N/A	Pending	Pending	Pending	1	1	2	6

Key Moments - 3 Insights

Why does the function call itself with n-1 instead of n?

Because the recursion needs to reach the base case (n=0). Calling with n-1 reduces the input step-by-step, as shown in execution_table steps 1 to 4.

Why is the base case pattern '0 => 1' important?

It stops the recursion by returning a value without further calls. Without it, the function would call itself forever. See step 4 in execution_table where base case returns 1.

What does the underscore (_) pattern mean in the match?

It matches any value not matched before (default case). Here it handles all n > 0, triggering recursive calls as in steps 1-3.

Visual Quiz - 3 Questions

Look at the execution_table, what is the return value when n=1 (step 5)?

A 2

B 0

C 1

D Pending

💡 Hint

Check the 'Return Value' column at step 5 in execution_table

At which step does the base case pattern match?

A Step 4

B Step 1

C Step 7

D Step 3

💡 Hint

Look for 'Base case (0)' in the 'Pattern Matched' column in execution_table

If the base case was missing, what would happen to the execution?

A Recursion would stop immediately

B Recursion would continue infinitely causing a stack overflow

C Function would return 0 for all inputs

D Function would return 1 for all inputs

💡 Hint

Refer to key_moments explanation about the importance of the base case

Concept Snapshot

Recursive pattern matching uses 'switch' to check input.
Base case pattern returns a value directly.
Default pattern calls function recursively with smaller input.
Recursion continues until base case is reached.
Results combine as recursion unwinds.
Useful for problems like factorial, Fibonacci, tree traversal.

Full Transcript

This example shows recursive pattern matching in C#. The function Factorial uses a switch expression to check the input number n. If n is zero, it returns 1 immediately (base case). Otherwise, it calls itself with n-1 and multiplies the result by n. The execution table traces each call and return, showing how recursion breaks down the problem and then combines results. The variable tracker shows how n and return values change step-by-step. Key moments clarify why the base case is needed and what the underscore pattern means. The quiz tests understanding of return values, base case location, and recursion behavior without a base case.