Recursion and Backtracking in Python

What is Recursion?

Recursion solves a problem by:

1. Base Case – defines when recursion should stop
2. Recursive Case – reduces the problem and calls itself
3. Progress – each call moves closer to the base case

---

Core Parts of a Recursive Solution

• Base Case: Prevents infinite recursion
• Recursive Relation: Defines how the problem is broken down
• Progress Toward Base Case: Input size must shrink

---

Example: Factorial

def factorial(n):
    if n == 0 or n == 1:   # base case
        return 1
    return n * factorial(n - 1)  # recursive case

print(factorial(5))  # 120

---

Each recursive call is placed on the call stack until it returns.
For deep recursion, this can cause a stack overflow (Python has a recursion limit).

---

Common Recursion Mistakes

• Missing base case → infinite recursion
• Not reducing problem size
• Incorrect return handling
• Too deep recursion (prefer iteration or DP when possible)

---

Recursion is commonly used in:

• Tree traversals
• Divide and conquer (merge sort)
• Depth-first search (DFS)
• Dynamic programming (top-down)

---

Example: Sum of an Array (Recursive)

def sum_array(arr, i=0):
    if i == len(arr):
        return 0
    return arr[i] + sum_array(arr, i + 1)

print(sum_array([1, 2, 3, 4]))  # 10

---

Example: Recursive Binary Search

def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1

    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

arr = [1, 3, 5, 7, 9]
print(binary_search_recursive(arr, 7, 0, len(arr) - 1))  # 3

---

Backtracking is used when:

• You must explore all possibilities
• You must satisfy constraints
• You want to stop early once a solution is found

---

Backtracking Pattern

1. Choose an option
2. Explore recursively
3. Undo the choice if it fails

---

Generic Backtracking Template

def backtrack(state):
    if goal_reached(state):
        save_answer(state)
        return

    for choice in choices(state):
        apply(choice, state)
        backtrack(state)
        undo(choice, state)

---

Place N queens on an N x N chessboard such that no two queens attack each other.

Constraints

A queen attacks:

• Same row
• Same column
• Same diagonals

---

Backtracking Idea

• Place queens row by row
• For each row, try all columns
• Place queen if safe
• Backtrack if no valid placement exists

---

Implementation

def solve_n_queens(n):
    board = [["."] * n for _ in range(n)]
    cols = set()
    diag1 = set()  # r - c
    diag2 = set()  # r + c
    results = []

    def backtrack(r):
        if r == n:
            results.append(["".join(row) for row in board])
            return

        for c in range(n):
            if c in cols or (r - c) in diag1 or (r + c) in diag2:
                continue

            board[r][c] = "Q"
            cols.add(c)
            diag1.add(r - c)
            diag2.add(r + c)

            backtrack(r + 1)

            board[r][c] = "."
            cols.remove(c)
            diag1.remove(r - c)
            diag2.remove(r + c)

    backtrack(0)
    return results

print(len(solve_n_queens(4)))  # 2

Complexity

• Worst case: Exponential
• Optimized checks using sets: O(1) per check

---

Fill a 9 x 9 grid so that each row, column, and 3 x 3 box contains digits 1–9.

---

Backtracking Idea

1. Find an empty cell
2. Try digits 1–9
3. If valid, place digit and recurse
4. If failure, undo and try next digit

---

Implementation

def solve_sudoku(board):
    def is_valid(r, c, val):
        for j in range(9):
            if board[r][j] == val:
                return False

        for i in range(9):
            if board[i][c] == val:
                return False

        box_r = (r // 3) * 3
        box_c = (c // 3) * 3
        for i in range(box_r, box_r + 3):
            for j in range(box_c, box_c + 3):
                if board[i][j] == val:
                    return False

        return True

    def backtrack():
        for i in range(9):
            for j in range(9):
                if board[i][j] == ".":
                    for val in "123456789":
                        if is_valid(i, j, val):
                            board[i][j] = val
                            if backtrack():
                                return True
                            board[i][j] = "."
                    return False
        return True

    backtrack()
    return board

---

Find a path from the top-left to bottom-right in a maze.

• 1 → open cell
• 0 → blocked cell

---

Backtracking Idea

• From each cell, try moving right or down
• Mark path if valid
• Backtrack if dead end

---

Implementation (Right + Down Moves)

def rat_maze(maze):
    n = len(maze)
    sol = [[0] * n for _ in range(n)]

    def is_safe(x, y):
        return 0 <= x < n and 0 <= y < n and maze[x][y] == 1

    def backtrack(x, y):
        if x == n - 1 and y == n - 1:
            sol[x][y] = 1
            return True

        if is_safe(x, y):
            sol[x][y] = 1

            if backtrack(x + 1, y):
                return True
            if backtrack(x, y + 1):
                return True

            sol[x][y] = 0
            return False

        return False

    if backtrack(0, 0):
        return sol
    return None

maze = [
    [1, 0, 0, 0],
    [1, 1, 0, 1],
    [0, 1, 0, 0],
    [1, 1, 1, 1]
]

print(rat_maze(maze))

---

• Recursion breaks problems into smaller subproblems using base cases.
• Backtracking systematically explores choices and undoes them on failure.
• Classic problems like N-Queens, Sudoku, and Rat-in-a-Maze are ideal for mastering these techniques.
• Understanding recursion + backtracking builds strong foundations for DFS, graphs, trees, and constraint-based problems.