Recursion & Backtracking

intermediate5 problems· Prerequisites: Big O & Complexity, Arrays & Strings, Stacks & Queues

Recursion Basics

A recursive function calls itself with a smaller or simpler input until it reaches a base case (the simplest possible input).

Every recursive function needs:

Base case — the condition that stops the recursion
Recursive case — the function calling itself with modified input

The call stack tracks each recursive call. Too many recursive calls = stack overflow.

Approach	Time	Space	When to use
Iterative	O(n)	O(1)	Simple linear problems
Recursive	O(recursions)	O(depth)	Tree/graph traversal, divide & conquer
Memoized	O(states)	O(states)	Overlapping subproblems

Recursion vs iterationC#

// Iterative factorial — O(n) time, O(1) space
int FactorialIter(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) result *= i;
    return result;
}

// Recursive factorial — O(n) time, O(n) stack space
int FactorialRec(int n) {
    if (n <= 1) return 1;          // base case
    return n * FactorialRec(n - 1); // recursive case
}

// Fibonacci — naive: O(2ⁿ) time, O(n) stack space
int FibNaive(int n) {
    if (n <= 1) return n;
    return FibNaive(n - 1) + FibNaive(n - 2); // exponential!
}

// Fibonacci — memoized: O(n) time, O(n) space
int FibMemo(int n, Dictionary<int, int> memo = null) {
    memo ??= new Dictionary<int, int>();
    if (n <= 1) return n;
    if (memo.ContainsKey(n)) return memo[n];
    return memo[n] = FibMemo(n - 1, memo) + FibMemo(n - 2, memo);
}

Backtracking

Backtracking is a systematic way to try all possibilities. You make a choice, explore recursively, then undo the choice (backtrack) and try the next option.

Template:

Check if current state is a valid solution → add to results
Iterate through all possible choices at this step
Make the choice → recurse → undo the choice

Used for: permutations, subsets, combination sum, N-Queens, Sudoku solver.

Backtracking templateC#

// Generate all subsets (powerset) — O(2ⁿ)
IList<IList<int>> Subsets(int[] nums) {
    var result = new List<IList<int>>();
    var current = new List<int>();
    Backtrack(0);
    return result;

    void Backtrack(int start) {
        result.Add(new List<int>(current)); // add current subset

        for (int i = start; i < nums.Length; i++) {
            current.Add(nums[i]);            // choose
            Backtrack(i + 1);                // explore
            current.RemoveAt(current.Count - 1); // un-choose
        }
    }
}

// Generate all permutations — O(n!)
IList<IList<int>> Permute(int[] nums) {
    var result = new List<IList<int>>();
    var current = new List<int>();
    var used = new bool[nums.Length];
    Backtrack();
    return result;

    void Backtrack() {
        if (current.Count == nums.Length) {
            result.Add(new List<int>(current));
            return;
        }
        for (int i = 0; i < nums.Length; i++) {
            if (used[i]) continue;
            used[i] = true;
            current.Add(nums[i]);
            Backtrack();
            current.RemoveAt(current.Count - 1);
            used[i] = false;
        }
    }
}

Divide & Conquer

A recursive pattern where you:

Divide the problem into smaller subproblems
Conquer each subproblem recursively
Combine the results

Examples: Merge sort, quick sort, binary search, tree traversals.

Merge sort — classic divide & conquerC#

int[] MergeSort(int[] arr) {
    if (arr.Length <= 1) return arr;

    int mid = arr.Length / 2;
    var left = MergeSort(arr[..mid]);     // divide
    var right = MergeSort(arr[mid..]);    // divide

    return Merge(left, right);            // combine
}

int[] Merge(int[] left, int[] right) {
    var result = new int[left.Length + right.Length];
    int i = 0, j = 0, k = 0;

    while (i < left.Length && j < right.Length)
        result[k++] = left[i] <= right[j] ? left[i++] : right[j++];

    while (i < left.Length) result[k++] = left[i++];
    while (j < right.Length) result[k++] = right[j++];

    return result;
}
// O(n log n) time, O(n) space

Common Interview Patterns

Subsets (powerset) — for each element, include or exclude
Permutations — try each unused element at each position
Combination sum — pick elements (with/without repetition) to reach target
Generate parentheses — add open or close parenthesis, tracking counts
Tree traversal — DFS is naturally recursive (preorder/inorder/postorder)
Divide & conquer — merge sort, quick sort, maximum subarray