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

Problem

Compute 5! (5 factorial) by breaking it into smaller subproblems. Watch how the call stack grows and shrinks.

Recursion: factorial(5)Step 1 / 10

factorial(5)5 × factorial(4)

Call factorial(5) — stack frame pushed

Speed:

Active Done Waiting

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

Recursion vs Iteration

Recursion works best when:

The problem has a natural recursive structure (trees, graphs, divide and conquer)
The input can be defined recursively (lists, trees, combinatorial search)
The backtracking pattern fits (try choice, recurse, undo)
Code clarity and brevity matter more than performance

Iteration is better when:

Stack depth could be a problem (deep recursion = stack overflow)
The problem is linear (looping through an array)
Performance is critical (function calls have overhead)
The recursion would have duplicate work (use memoization or iteration)

Decision guide:

Pattern	Use recursion?	Why
Tree traversal	Yes	Natural recursive structure
Array iteration	No	Simple loop is faster
Permutations / subsets	Yes	Backtracking is naturally recursive
Factorial / Fibonacci	Memoized recursion or iteration	Naive recursion is wasteful
Divide & conquer (merge sort)	Yes	Divide + combine is recursive
BFS / level order	No	Queue iteration is simpler

Warning signs for recursion:

Depth could exceed 1000 (stack overflow)
Problem has no overlapping subproblems (simple iteration works)
You need to pass mutable state through many levels

Common Mistakes / Gotchas

Missing base case (infinite recursion) Without a base case, recursion never stops and you get stack overflow. Always write the base case first.

Not returning the recursive result factorial(n) = n * factorial(n - 1) - if you forget the return, the function returns undefined / null. Always return the recursive result.

Naive Fibonacci is O(2ⁿ) fib(n) = fib(n-1) + fib(n-2) without memoization recomputes the same values exponentially. Use memoization or iteration.

Stack overflow from deep recursion Each call adds a stack frame. For depth > 1000 (Python), > 10000 (C#/Java/C++), you risk overflow. Consider iterative alternatives for linear problems.

Modifying shared state during recursion If you pass a mutable list down recursive calls and mutate it, you need to undo (backtrack) or copy. Forgetting the undo step corrupts sibling branches.

Confusing recursion depth with problem size A recursive function on a balanced tree of n nodes has O(log n) depth, not O(n). Depth depends on structure, not total elements.