Recursion and Backtracking

Recursion Fundamentals

A recursive function calls itself to solve smaller subproblems. Every recursive solution has:

Base case: Termination condition — solves the problem directly.
Recursive case: Breaks the problem into smaller subproblems and combines results.

FUNCTION FACTORIAL(n)
    IF n = 0 THEN RETURN 1            // base case
    RETURN n * FACTORIAL(n - 1)        // recursive case

FUNCTION FIBONACCI(n)
    IF n = 0 THEN RETURN 0
    IF n = 1 THEN RETURN 1
    RETURN FIBONACCI(n - 1) + FIBONACCI(n - 2)   // naive: O(2^n)

Call Stack

Each recursive call adds a stack frame containing local variables, parameters, and return address. Deep recursion can cause stack overflow.

factorial(4) → factorial(3) → factorial(2) → factorial(1) → factorial(0)
                                                              returns 1
                                                returns 1×1 = 1
                                 returns 2×1 = 2
                  returns 3×2 = 6
returns 4×6 = 24

Tail Recursion

A function is tail recursive if the recursive call is the last operation. Tail-recursive functions can be optimized into loops (tail call optimization — TCO).

// Not tail recursive: multiplication happens AFTER the recursive call
FUNCTION FACTORIAL(n)
    IF n = 0 THEN RETURN 1
    RETURN n * FACTORIAL(n - 1)

// Tail recursive: recursive call is the last operation
FUNCTION FACTORIAL_TAIL(n, acc)
    IF n = 0 THEN RETURN acc
    RETURN FACTORIAL_TAIL(n - 1, n * acc)

Note: Rust does not guarantee TCO (unlike some functional languages). Convert to iteration for guaranteed stack safety in Rust.

Recursion vs Iteration

Any recursive algorithm can be converted to iterative using an explicit stack. Iteration avoids stack overflow risk and function call overhead.

When to use recursion: Tree/graph traversal, divide-and-conquer, problems with natural recursive structure. Code is often cleaner and more readable.

When to use iteration: Deep recursion risk, performance-critical code, when TCO is not guaranteed.

Backtracking

Backtracking is a systematic way to explore all possible solutions by building candidates incrementally and abandoning ("backtracking" from) candidates as soon as they violate constraints.

General Template

PROCEDURE BACKTRACK(state, solutions)
    IF IS_SOLUTION(state)
        ADD state TO solutions
        RETURN

    FOR EACH choice IN CANDIDATES(state)
        IF IS_VALID(state, choice)
            MAKE_CHOICE(state, choice)         // choose
            BACKTRACK(state, solutions)        // explore
            UNDO_CHOICE(state, choice)         // un-choose (backtrack)

N-Queens Problem

Place n queens on an n×n chessboard so no two queens attack each other.

FUNCTION SOLVE_N_QUEENS(n)
    solutions ← empty list
    queens ← empty list       // queens[i] = column of queen in row i
    PLACE_QUEENS(n, queens, solutions)
    RETURN solutions

PROCEDURE PLACE_QUEENS(n, queens, solutions)
    IF length(queens) = n
        ADD copy of queens TO solutions
        RETURN

    row ← length(queens)
    FOR col ← 0 TO n - 1
        IF IS_SAFE(queens, row, col)
            APPEND col TO queens
            PLACE_QUEENS(n, queens, solutions)
            REMOVE last element FROM queens   // backtrack

FUNCTION IS_SAFE(queens, row, col)
    FOR r ← 0 TO length(queens) - 1
        c ← queens[r]
        IF c = col OR (row - r) = |col - c|
            RETURN false    // same column or diagonal
    RETURN true

Solutions for n: n=4 has 2, n=8 has 92, n=12 has 14200. Time: O(n!) worst case, but pruning reduces this dramatically.

Sudoku Solver

FUNCTION SOLVE_SUDOKU(board)
    // Find next empty cell
    (row, col) ← FIND_EMPTY(board)
    IF no empty cell found THEN RETURN true   // all filled — solved!

    FOR num ← 1 TO 9
        IF IS_VALID_PLACEMENT(board, row, col, num)
            board[row][col] ← num
            IF SOLVE_SUDOKU(board) THEN RETURN true
            board[row][col] ← 0   // backtrack
    RETURN false   // no valid number for this cell — trigger backtracking

Subset Sum

Find all subsets of a set that sum to a target value.

PROCEDURE SUBSET_SUM(nums, target, idx, current, results)
    IF target = 0
        ADD copy of current TO results
        RETURN
    IF target < 0 OR idx ≥ length(nums) THEN RETURN

    // Include nums[idx]
    APPEND nums[idx] TO current
    SUBSET_SUM(nums, target - nums[idx], idx + 1, current, results)
    REMOVE last element FROM current   // backtrack

    // Exclude nums[idx]
    SUBSET_SUM(nums, target, idx + 1, current, results)

Permutation Generation

PROCEDURE PERMUTATIONS(arr, start, results)
    IF start = length(arr)
        ADD copy of arr TO results
        RETURN
    FOR i ← start TO length(arr) - 1
        SWAP(arr[start], arr[i])
        PERMUTATIONS(arr, start + 1, results)
        SWAP(arr[start], arr[i])   // backtrack

Combination Generation

PROCEDURE COMBINATIONS(n, k, start, current, results)
    IF length(current) = k
        ADD copy of current TO results
        RETURN
    // Pruning: need k - length(current) more elements, so stop if not enough left
    FOR i ← start TO n - (k - length(current))
        APPEND i TO current
        COMBINATIONS(n, k, i + 1, current, results)
        REMOVE last element FROM current   // backtrack

Constraint Propagation

Reduce the search space by propagating the consequences of each choice.

Example in Sudoku: When placing a number, immediately eliminate it from the row, column, and box. If any cell has only one possible value, fill it in. Repeat (forward checking).

Arc consistency (AC-3): For constraint satisfaction problems, ensure that for every value in a variable's domain, there exists a consistent value in every neighbor's domain.

Constraint propagation + backtracking = much faster than naive backtracking.

Pruning Strategies

Feasibility Pruning

Abandon a branch as soon as a constraint is violated (standard backtracking).

If we can compute an upper bound (for maximization) or lower bound (for minimization) on the best solution achievable from the current state, and it's worse than the best solution found so far, prune.

Symmetry Breaking

If the problem has symmetry, only explore one representative from each equivalence class.

Example: N-queens. The first queen can be placed only in the left half of the first row (solutions in the right half are reflections).

Ordering Heuristics

Most Constrained Variable (MRV / fail-first): Choose the variable with the fewest remaining legal values. Detects failures earlier.
Least Constraining Value (LCV): Try values that rule out the fewest choices for other variables.

Branch and Bound

A systematic search technique for optimization problems that combines backtracking with bounding.

1. Maintain the best solution found so far (incumbent).
2. At each node, compute a bound on the best possible solution in the subtree.
3. If the bound is worse than the incumbent, prune.
4. Otherwise, branch: explore children.

Applications: Integer programming, TSP, knapsack, scheduling, combinatorial auctions.

Relation to backtracking: Branch and bound = backtracking + bounding. Standard backtracking only prunes infeasible solutions. B&B also prunes suboptimal solutions.

Applications in CS

Compilers: Parsing (recursive descent). Type inference with backtracking.
AI: Game tree search (backtracking + alpha-beta pruning). Constraint satisfaction problems.
Combinatorics: Generating all permutations, combinations, subsets, partitions.
Puzzle solving: Sudoku, crosswords, n-queens, maze solving.
Optimization: Integer programming (branch and bound), SAT solvers (DPLL with backtracking).
Database query optimization: Explore join orderings with pruning.
Testing: Generate test cases systematically (all valid inputs up to a size).