Recursion solves a problem in terms of smaller versions of itself. Divide and conquer splits, solves, and combines; backtracking explores choices and undoes them. The mental tools behind trees, graphs, and DP.
A recursive function solves a problem by calling itself on a smaller input until it hits a base case that stops the recursion. Every correct recursion needs two things: a base case (the smallest solvable version) and a recursive step that makes progress toward it. Get those right and complex traversals become a few lines; get the base case wrong and you get infinite recursion.
# every recursion = a BASE CASE + a step toward it
def factorial(n):
if n <= 1: # base case — stops the recursion
return 1
return n * factorial(n - 1) # recursive step — smaller input
# the call stack does the bookkeeping:
# factorial(3) -> 3 * factorial(2) -> 3 * (2 * factorial(1)) -> 3*2*1 = 6
# a missing/wrong base case = infinite recursion -> RecursionError.
# recursion trades an explicit stack for the call stack — clearer, but
# deep recursion can overflow it (Python's limit ~1000 frames).Divide and conquer is a recursion shape: split the problem into independent subproblems, solve each recursively, and combine the results. Merge sort is the canonical example (split, sort halves, merge). The pattern wins when the subproblems are independent and combining is cheap, and it often yields O(n log n) from the halving.
# divide and conquer: split -> solve each -> combine
def max_element(a):
if len(a) == 1: # base case
return a[0]
mid = len(a) // 2
left = max_element(a[:mid]) # solve each half independently
right = max_element(a[mid:])
return max(left, right) # combine cheaply
# same shape as merge sort. The halving gives log n levels of recursion.
# Use when subproblems are INDEPENDENT and combining is cheap.Backtracking explores a tree of choices: at each step you make a choice, recurse to explore its consequences, then undo the choice to try the next one. It systematically generates all valid combinations, permutations, or paths, and prunes branches that cannot lead to a solution. It is how you solve constraint problems like Sudoku, N-Queens, and subset generation.
# generate all subsets of nums via choose / explore / un-choose
def subsets(nums):
result = []
path = []
def backtrack(start):
result.append(path[:]) # record the current subset (a copy)
for i in range(start, len(nums)):
path.append(nums[i]) # CHOOSE
backtrack(i + 1) # EXPLORE with that choice
path.pop() # UNDO (backtrack)
backtrack(0)
return result
subsets([1, 2, 3])
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]
# the choose/recurse/undo skeleton solves N-Queens, permutations, Sudoku...Naive backtracking can explore an exponential number of branches, so the art is pruning — abandoning a partial solution the moment it violates a constraint, before exploring further. Good pruning turns an intractable search into a fast one. The N-Queens solver below rejects a placement immediately if it is attacked, cutting the vast majority of the search tree.
# N-Queens: place N queens so none attack each other. Prune illegal placements.
def solve_n_queens(n):
cols, diag1, diag2 = set(), set(), set()
solutions, board = [], []
def backtrack(r):
if r == n:
solutions.append(board[:]); return
for c in range(n):
if c in cols or (r-c) in diag1 or (r+c) in diag2:
continue # PRUNE: this square is attacked
cols.add(c); diag1.add(r-c); diag2.add(r+c); board.append(c)
backtrack(r + 1) # explore
cols.remove(c); diag1.remove(r-c); diag2.remove(r+c); board.pop() # undo
backtrack(0)
return solutions
# pruning attacked squares avoids exploring the huge majority of placements.