Nitinn S Kulkarni

Posted on Apr 4

Part 5: Recursion and Backtracking – Solving Complex Problems Elegantly in Python

#python #dsa #interview #programming

🚀 Introduction

Recursion and backtracking are two core techniques that unlock powerful problem-solving patterns — especially when dealing with trees, permutations, combinations, puzzles, and pathfinding.

In this post, we’ll explore:

✅ What recursion is and how it works

✅ Visualizing the call stack

✅ Backtracking explained with templates

✅ Real-world problems like permutations, combinations, and Sudoku solver

✅ Tips to avoid common pitfalls like infinite recursion and stack overflows

🔄 1️⃣ What is Recursion?

Recursion is when a function calls itself to solve a smaller sub-problem.

🔹 Classic Example: Factorial


def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

🧠 Think in 3 parts:

1. Base case – when to stop

2. Recursive case – how the problem shrinks

3. Stack – Python uses a call stack to track function calls

🧠 Visualizing the Call Stack


factorial(3)
=> 3 * factorial(2)
       => 2 * factorial(1)
              => 1 * factorial(0)
                     => 1

Each recursive call is paused until the next one returns. This LIFO behavior is similar to a stack.

🧩 2️⃣ What is Backtracking?

Backtracking is a strategy to solve problems by exploring all possibilities and undoing decisions when needed.

It’s used when:

1. You’re generating permutations or combinations

2. Solving constraint problems (like Sudoku)

3. Exploring paths in a grid or tree

🔧 3️⃣ Backtracking Template


def backtrack(path, choices):
    if goal_reached(path):
        results.append(path)
        return

    for choice in choices:
        if is_valid(choice):
            make_choice(choice)
            backtrack(path + [choice], updated_choices)
            undo_choice(choice)

This is the core idea behind all backtracking solutions.

🧪 4️⃣ Example: Generate All Permutations


def permute(nums):
    results = []

    def backtrack(path, remaining):
        if not remaining:
            results.append(path)
            return

        for i in range(len(remaining)):
            backtrack(path + [remaining[i]], remaining[:i] + remaining[i+1:])

    backtrack([], nums)
    return results

print(permute([1, 2, 3]))

🎯 5️⃣ Example: N-Queens Problem

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


def solve_n_queens(n):
    solutions = []

    def backtrack(row, cols, diag1, diag2, board):
        if row == n:
            solutions.append(["".join(r) for r in board])
            return

        for col in range(n):
            if col in cols or (row + col) in diag1 or (row - col) in diag2:
                continue
            board[row][col] = 'Q'
            backtrack(row + 1, cols | {col}, diag1 | {row + col}, diag2 | {row - col}, board)
            board[row][col] = '.'

    board = [["."] * n for _ in range(n)]
    backtrack(0, set(), set(), set(), board)
    return solutions

🔢 6️⃣ Example: Combinations


def combine(n, k):
    results = []

    def backtrack(start, path):
        if len(path) == k:
            results.append(path[:])
            return
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()

    backtrack(1, [])
    return results

✅ Backtracking often involves modifying state, recursing, and then undoing that change.

🎲 7️⃣ Example: Solving a Sudoku Board


def solve_sudoku(board):
    def is_valid(r, c, val):
        for i in range(9):
            if board[r][i] == val or board[i][c] == val or board[r//3*3 + i//3][c//3*3 + i%3] == val:
                return False
        return True

    def backtrack():
        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    for num in map(str, range(1, 10)):
                        if is_valid(r, c, num):
                            board[r][c] = num
                            if backtrack():
                                return True
                            board[r][c] = "."
                    return False
        return True

    backtrack()

📌 A great example of recursive state search with constraint pruning.

🧠 8️⃣ Tips and Best Practices

✅ Always define a base case

✅ Use sets or visited arrays to avoid cycles

✅ Use path[:] or path.copy() when passing lists

✅ Try to write recursive + backtracking templates once and reuse

⚠️ Be careful with Python's recursion limit (sys.setrecursionlimit())

🧪 Classic Problems to Practice

Problem	Type
Fibonacci	Recursion + Memoization
Permutations	Backtracking
N-Queens	Backtracking + Pruning
Sudoku Solver	Backtracking
Word Search in Grid	DFS + Backtracking
Letter Combinations of a Phone Number	Backtracking
Subsets / Combinations	Backtracking

✅ Summary

✔️ Recursion is calling a function within itself to break problems into sub-problems
✔️ Backtracking is about exploring, committing, and undoing choices
✔️ Use backtracking for problems involving all possible combinations/permutations
✔️ Python makes recursion intuitive with simple syntax – just be mindful of stack depth
✔️ Think in terms of state, choices, and constraints
🔜 Coming Up Next:

👉 Part 6: Sorting Algorithms – From Bubble Sort to Merge Sort (with Python Code and Complexity Analysis)

We’ll cover:

1. Selection, Bubble, Insertion Sort


Merge Sort and Quick Sort
Built-in sort and Timsort
When to use what

DEV Community