Recursion is a technique where a function calls itself to solve smaller instances of the same problem.
Backtracking is a systematic problem-solving approach (usually implemented with recursion) that explores possible choices, and undoes (backtracks) them when they lead to a dead end.
These concepts are fundamental in DSA and appear frequently in interviews and competitive programming.
They are heavily used in:
- Permutations and combinations
- Subset generation
- Constraint satisfaction problems (N-Queens, Sudoku)
- Pathfinding in grids and mazes
- DFS-based graph and tree problems
Understanding Recursion and Its Applications
What is Recursion?
Recursion solves a problem by:
- Base Case – defines when recursion should stop
- Recursive Case – reduces the problem and calls itself
- 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
Recursion Stack (Important Concept)
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)
Implementing Recursive Algorithms in Python
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
Introduction to Backtracking
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
- Choose an option
- Explore recursively
- 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)
Classic Backtracking Problems
1) N-Queens Problem
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
2) Sudoku Solver
Fill a 9 x 9 grid so that each row, column, and 3 x 3 box contains digits 1–9.
Backtracking Idea
- Find an empty cell
- Try digits
1–9 - If valid, place digit and recurse
- 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
3) Rat in a Maze Problem
Find a path from the top-left to bottom-right in a maze.
1→ open cell0→ 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))
Summary
- 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.
Leave a Reply