Backtracking & Recursion: Techniques, Algorithms & Complexity

Core Concepts: Recursion vs. Backtracking

Recursion: The Self-Referential Approach

Definition: A method where a function calls itself to solve smaller instances of the same problem. Key Idea: Break a problem into identical subproblems until reaching a base case.

flowchart TD
    A["Problem P(n)"] -->|"Divide"| B["Subproblem P(n-1)"]
    B -->|"Divide"| C["Subproblem P(n-2)"]
    C -->|"Base Case"| D["P(1) = Known Solution"]
    D -->|"Return"| C
    C -->|"Return"| B
    B -->|"Return"| A

Example: Factorial Calculation

def factorial(n):
    if n == 0: return 1  # Base case
    return n * factorial(n-1)  # Recursive call

Trace for factorial(3):

Visualization of Call Stack:

factorial(3)
├── 3 * factorial(2)
│   ├── 2 * factorial(1)
│   │   ├── 1 * factorial(0)
│   │   │   └── 1 (returned)
│   │   └── 1 (returned)
│   └── 2 (returned)
└── 6 (returned)

Backtracking: Systematic Trial-and-Error

Definition: A high-level algorithmic technique for solving problems by incrementally building candidates and abandoning ("backtracking") those that fail to satisfy constraints.

Key Idea:

1. Make a choice (e.g., place a queen on a chessboard).
2. Recursively explore consequences of that choice.
3. Undo the choice if it leads to a dead end.

Comparison Table:

Algorithmic Applications

1. Subset Sum Problem

Problem: Given a set of integers S and a target sum X, find a subset of S that sums to X. Algorithm:

1. Sort the set in descending order (optimization).
2. Recursively explore including/excluding each element.

flowchart TD
    A["SubsetSum(S, X)"] --> B["If X=0: return true"]
    A --> C["If S is empty: return false"]
    A --> D["Include S[0]"] --> E["SubsetSum(S[1:], X-S[0])"]
    A --> F["Exclude S[0]"] --> G["SubsetSum(S[1:], X)"]

Worked Example: S = {3, 5, 2, 4, 1}, X = 8 Trace:

Visualization of Search Tree:

          {3,5,2,4,1}, 8
         /               \
{3,2,4,1},3 (True)    {3,2,4,1},8 (False)
       /       \
{2,4,1},0 (True) {2,4,1},3 (False)

2. N-Queens Problem

Problem: Place N queens on an N×N chessboard so that no two queens threaten each other. Algorithm:

1. Place a queen in the first column.
2. Recursively place queens in subsequent columns, ensuring no conflicts.
3. Backtrack if a conflict arises.

def solve_n_queens(n):
    def is_safe(board, row, col):
        for i in range(row):
            if board[i] == col or abs(board[i] - col) == abs(i - row):
                return False
        return True

    def backtrack(row, board, solutions):
        if row == n:
            solutions.append(board.copy())
            return
        for col in range(n):
            if is_safe(board, row, col):
                board[row] = col
                backtrack(row + 1, board, solutions)
                board[row] = -1  # Backtrack

    solutions = []
    backtrack(0, [-1] * n, solutions)
    return solutions

Trace for N=4:

Visualization of Board States:

Step 1: Q . . .
Step 2: Q . Q .
Step 3: Q . . Q (Conflict)
Step 4: Q . Q Q (Solution)

Complexity Analysis

Time Complexity of Backtracking

• Worst Case: Exponential (O(2^n) for subset sum, O(N!) for N-Queens).
• Optimizations:
  • Pruning: Eliminate invalid paths early (e.g., in N-Queens, skip columns under attack).
  • Ordering: Sort inputs to reduce search space (e.g., descending order in subset sum).

Example: Miller-Rabin Primality Test

• Complexity: O(k log³ n) for k iterations.
• Trace for n=53:

  Step	Test	Result
  1	53 ≡ 2^10 mod 51	1 ≡ 1024 mod 51
  2	1024 mod 51 = 1	Prime

In the Real World

1. Pathao/Daraz Order Routing:

   • Idea: Backtracking is used to dynamically reroute delivery paths when obstacles (e.g., traffic, closed roads) are detected.
   • How: The system recursively explores alternative routes, backtracking from dead ends until a feasible path is found.

2. Nepal Rastra Bank Loan Approval:

   • Idea: Recursive validation of loan eligibility criteria (e.g., income, credit score, collateral).
   • How: The bank’s system checks each criterion hierarchically, returning only if all sub-conditions (e.g., "income ≥ threshold and credit score ≥ X") are met.

3. eSewa Bill Payment:

   • Idea: Backtracking ensures that partial payments or failed transactions are rolled back to maintain system consistency.
   • How: If a payment fails mid-process (e.g., insufficient funds), the system backtracks to the initial state and notifies the user.

Exam Tip

1. Define Clearly:

   • Recursion = "A function calling itself with smaller inputs."
   • Backtracking = "A systematic search with undo steps for invalid choices."

2. Trace Algorithms:

   • For subset sum/N-Queens, show all recursive calls and backtracking steps in tables.
   • Example: For S = {6, 4, 5, 6, 9}, X = 11, trace both inclusion and exclusion paths.

3. Complexity Shortcuts:

   • Memorize:
     • Subset sum: O(2^n) (exponential).
     • N-Queens: O(N!) (factorial).
   • For Miller-Rabin: State O(k log³ n) and explain k is the number of rounds.

4. Real-World Links:

   • Tie traces to Nepali apps (e.g., "Like Pathao’s route-finding, backtracking explores alternative paths when roads are blocked").
   • Avoid vague answers like "used in AI"; specify how (e.g., "constraint satisfaction in scheduling").

5. Code + Trace:

   • Always provide pseudocode for backtracking algorithms and a step-by-step trace (table format).
   • Example: For factorial(4), show the call stack and return values explicitly.