Recursion and backtracking

Recursion is a programming technique where a function calls itself to solve smaller instances of a problem. Recursive thinking is a powerful way to solve complex problems by breaking them down into simpler sub-problems. Backtracking is an extension of recursion that involves exploring multiple possible solutions and abandoning (backtracking) paths that don’t lead to a solution.

Recursive Thinking

Recursive Thinking involves solving a problem by dividing it into smaller, similar sub-problems. Recursive algorithms are often composed of two main components:

1. Base Case: The simplest instance of the problem, which can be solved without further recursion. Base cases prevent infinite recursion by terminating the recursive calls.
2. Recursive Case: Defines how the problem should be broken down and includes a call to the same function with modified arguments that bring it closer to the base case.

Example: Factorial Calculation

The factorial of a non-negative integer ( n ) is calculated as:

• Base Case: ( n \= 0 ) or ( n \= 1 ) returns 1
• Recursive Case: ( n! \= n (n-1)! )

def factorial(n: int) -> int:
    # Base case
    if n <= 1:
        return 1
    # Recursive case
    return n * factorial(n - 1)

# Example usage
print(factorial(5))  # Output: 120

In this example, each call to factorial reduces ( n )by 1 until reaching the base case, where n is 1, and returns 1. Then, each call returns its result up the call stack.

Base Cases and Recursive Cases

Base Cases and Recursive Cases are essential components in any recursive function. A well-defined base case ensures that recursion terminates, while the recursive case allows the function to solve the problem incrementally.

Example: Fibonacci Sequence

The Fibonacci sequence is defined as:

• Base Cases: ( F(0) \= 0 ) and ( F(1) \= 1 )
• Recursive Case: ( F(n) \= F(n-1) + F(n-2) )

def fibonacci(n: int) -> int:
    # Base cases
    if n == 0:
        return 0
    elif n == 1:
        return 1
    # Recursive case
    return fibonacci(n - 1) + fibonacci(n - 2)

# Example usage
print(fibonacci(5))  # Output: 5 (sequence: 0, 1, 1, 2, 3, 5)

Backtracking Algorithms

Backtracking is a technique to explore all possible solutions to a problem by incrementally building candidates and discarding solutions that don’t satisfy the problem constraints (i.e., “backtracking” when a path leads to an invalid solution). It’s commonly used in problems like combinatorial search, constraint satisfaction, and puzzles.

Key Elements of Backtracking

1. Candidate Solution: A partially constructed solution that we are currently working on.
2. Constraints Check: A way to test if the candidate is valid or violates any constraints.
3. Backtrack Step: If a candidate is invalid, backtrack by removing the last step and trying an alternative.

Example: Solving the N-Queens Problem

The N-Queens problem is a classic example of backtracking, where we place ( N ) queens on an ( N N ) chessboard such that no two queens threaten each other (no two queens share the same row, column, or diagonal).

def solve_n_queens(n: int) -> list:
    result = []
    board = [-1] * n  # Initialize the board
    
    def is_valid(row, col):
        for r in range(row):
            c = board[r]
            if c == col or abs(c - col) == abs(r - row):  # Check column and diagonal conflicts
                return False
        return True
    
    def place_queen(row):
        if row == n:
            result.append(board[:])  # Add a solution (deep copy)
            return
        for col in range(n):
            if is_valid(row, col):
                board[row] = col  # Place queen
                place_queen(row + 1)  # Recurse to place next queen
                board[row] = -1  # Backtrack by removing queen
    
    place_queen(0)
    return result

# Example usage
solutions = solve_n_queens(4)
print(f"Number of solutions: {len(solutions)}")  # Output: Number of solutions: 2
print(solutions)  # Example solutions for 4x4 board

Explanation of N-Queens Backtracking

Candidate Solution: Each recursive call attempts to place a queen in one row.

1. Constraints Check: The is_valid function checks if the placement is safe (no other queens in the same column or diagonal).
2. Backtracking: If placing a queen doesn’t lead to a solution, remove it (reset the column to -1) and try the next column.

Common Backtracking Problems

1. Permutations and Combinations: Generate all possible permutations or combinations of a set.
2. Sudoku Solver: Fill a 9x9 grid based on Sudoku rules.
3. Subset Sum Problem: Find all subsets of a set that sum to a target value.
4. Maze Solving: Find a path through a maze.

Advantages and Limitations of Backtracking

Advantages:

• Allows exhaustive search of all solutions.
• Works well for combinatorial and constraint satisfaction problems.

Limitations:

• It can be slow due to the exponential number of possibilities.
• Pruning unnecessary paths (using constraints) is essential for efficiency.