🚀 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
Top comments (0)