Recursion and Backtracking in C#

Recursion and Backtracking in C#: Concepts, Patterns, and Classic Problems

Recursion and backtracking are essential techniques in algorithmic problem solving. They appear in everything from tree traversal to solving puzzles like Sudoku and N-Queens. In this post, you’ll learn how these concepts work, how to apply them in C#, and how to identify problems where recursion and backtracking shine.

What Is Recursion?

Recursion is a method where a function calls itself to solve smaller instances of the same problem. Every recursive function must have:

• A base case: condition to stop recursion
• A recursive case: logic to reduce the problem size

Real-World Analogy:

Imagine Russian nesting dolls. Each doll opens to reveal a smaller one, until the smallest doll (base case) is reached.

C# Example: Factorial

int Factorial(int n)
{
    if (n == 0 || n == 1) return 1;
    return n * Factorial(n - 1);
}

Common Recursive Patterns:

• Factorial
• Fibonacci numbers
• Reverse a string

What Is Backtracking?

Backtracking is a refined form of recursion used for exploration and constraint satisfaction. It builds candidates for solutions and abandons them (backtracks) when it determines they won’t work.

Key Characteristics:

• Tries all possibilities
• Abandons path when constraints are violated
• Efficient when combined with pruning

Template for Backtracking in C

void Backtrack(List<string> result, StringBuilder current, int depth)
{
    if (/* base case */)
    {
        result.Add(current.ToString());
        return;
    }

    for (int i = 0; i < choices.Length; i++)
    {
        // make a choice
        current.Append(choices[i]);

        // explore
        Backtrack(result, current, depth + 1);

        // undo the choice
        current.Length--;
    }
}

Backtracking Use Cases and Examples

1. Subset Generation (Power Set)

void Subsets(int[] nums, int index, List<int> current, List<List<int>> result)
{
    if (index == nums.Length)
    {
        result.Add(new List<int>(current));
        return;
    }

    // Include nums[index]
    current.Add(nums[index]);
    Subsets(nums, index + 1, current, result);

    // Exclude nums[index]
    current.RemoveAt(current.Count - 1);
    Subsets(nums, index + 1, current, result);
}

2. String Permutations

void Permute(char[] chars, int start, List<string> result)
{
    if (start == chars.Length)
    {
        result.Add(new string(chars));
        return;
    }

    for (int i = start; i < chars.Length; i++)
    {
        (chars[start], chars[i]) = (chars[i], chars[start]);
        Permute(chars, start + 1, result);
        (chars[start], chars[i]) = (chars[i], chars[start]);
    }
}

3. N-Queens Problem

bool IsSafe(int[] board, int row, int col)
{
    for (int i = 0; i < row; i++)
        if (board[i] == col || Math.Abs(board[i] - col) == row - i)
            return false;
    return true;
}

void SolveNQueens(int row, int[] board, List<int[]> results)
{
    int n = board.Length;
    if (row == n)
    {
        results.Add((int[])board.Clone());
        return;
    }

    for (int col = 0; col < n; col++)
    {
        if (IsSafe(board, row, col))
        {
            board[row] = col;
            SolveNQueens(row + 1, board, results);
        }
    }
}

Tips for Writing Recursive & Backtracking Code

• Always define a clear base case
• Use helper methods to keep recursion parameters clean
• Avoid unnecessary memory allocation
• Optimize with pruning and early exits

Practice Problems

1. Print all permutations of a string
2. Generate all subsets of a list
3. Solve N-Queens for n = 4
4. Sudoku solver
5. Generate valid parentheses (n pairs)