Recursion and Backtracking

This document covers the fundamental concepts of recursion and backtracking in the context of Data Structures and Algorithms (DSA).

Recursion

Recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem.

Key Concepts

• Base Case: The condition under which the recursion stops.
• Recursive Step: The part of the function that calls itself.

Example: Factorial

function factorial(n) {
  // Base case
  if (n === 0) {
    return 1;
  }
  // Recursive step
  return n * factorial(n - 1);
}

Backtracking

Backtracking is a general algorithmic technique that considers searching every possible combination in order to solve a computational problem. It is a refined brute force approach that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.

Key Concepts

• State Space Tree: The set of all possible states of a problem.
• Pruning: The process of discarding parts of the search space that will not lead to a solution.

Example: N-Queens Problem

A classic example of backtracking is the N-Queens problem, where the goal is to place N chess queens on an N×N chessboard so that no two queens threaten each other.