🚀 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)
=> 1Each 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