Recursion & Backtracking

Recursion is an algorithmic technique where a function calls itself to solve a smaller instance of the exact same problem.

The Two Rules of Recursion

Every recursive function MUST have two things to prevent infinite loops (Stack Overflow):

1. Base Case: A condition where the function stops calling itself and returns a value.
2. Recursive Step: The part where the function calls itself, moving closer to the base case with every call.

Simple Example: Factorial

$N! = N \times (N-1)!$

function factorial(n: number): number {
  // Base Case
  if (n <= 1) return 1;
  
  // Recursive Step
  return n * factorial(n - 1);
}

Backtracking

Backtracking is an algorithmic paradigm built on top of Recursion. It systematically searches for a solution to a problem among all available options by building a solution incrementally. If it reaches a point where it realizes the current path is a "dead end" (it violates the problem constraints), it backs up (backtracks) to the previous step and tries a different path.

Real-Life Analogy

Think of Solving a Sudoku Puzzle. You put a 1 in the first empty box. Then you move to the next box and try a 2. You keep going until you hit a box where NO numbers from 1-9 are valid without breaking Sudoku rules. Instead of starting the entire puzzle over, you backtrack to the previous box, erase the number, and try the next valid number.

Classic Problem: Permutations

Given an array [1, 2, 3], return all possible arrangements.

function permute(nums: number[]): number[][] {
  const results: number[][] = [];
  
  function backtrack(currentPermutation: number[], used: boolean[]) {
    // 1. Base Case (We found a full permutation)
    if (currentPermutation.length === nums.length) {
      results.push([...currentPermutation]); // Push a COPY!
      return;
    }
    
    // 2. Explore all options
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue; // Skip numbers already in our permutation
      
      // Make a choice
      currentPermutation.push(nums[i]);
      used[i] = true;
      
      // Explore down this path
      backtrack(currentPermutation, used);
      
      // BACKTRACK! Undo the choice so we can try the next loop iteration
      currentPermutation.pop();
      used[i] = false;
    }
  }
  
  backtrack([], new Array(nums.length).fill(false));
  return results;
}

Time Complexity of Backtracking

Because backtracking explores almost every possible combination, it usually has terrible Time Complexities like $O(N!)$ (Factorial) or $O(2^N)$ (Exponential). It is strictly used when $N$ is very small (e.g., $N \le 12$) and you absolutely must find every possible combination.