
AI Computing
Lesson Content
Recursion and Backtracking
What is Recursion?
A function that calls itself to solve smaller versions of the same problem.
Key Components
- Base Case: When to stop recursing
- Recursive Case: How to break down the problem
- Progress: Each call moves toward base case
Simple Example: Factorial
codedef factorial(n): # Base case if n == 0 or n == 1: return 1 # Recursive case return n * factorial(n - 1) # factorial(5) = 5 * factorial(4) # = 5 * 4 * factorial(3) # = 5 * 4 * 3 * factorial(2) # = 5 * 4 * 3 * 2 * factorial(1) # = 5 * 4 * 3 * 2 * 1 # = 120
How Recursion Works: The Call Stack
codedef countdown(n): if n == 0: print("Blastoff!") else: print(n) countdown(n - 1) countdown(3)
Call Stack:
codecountdown(3) prints 3, calls countdown(2) countdown(2) prints 2, calls countdown(1) countdown(1) prints 1, calls countdown(0) countdown(0) prints "Blastoff!", returns returns to countdown(1) returns to countdown(2) returns to countdown(3)
Recursion vs Iteration
Recursive Sum
codedef recursive_sum(arr): if len(arr) == 0: return 0 return arr[0] + recursive_sum(arr[1:])
Iterative Sum
codedef iterative_sum(arr): total = 0 for num in arr: total += num return total
When to use recursion?
- Tree/graph traversal
- Divide and conquer algorithms
- Backtracking problems
- Natural recursive structure
When to use iteration?
- Simple loops
- Performance critical code
- Large datasets (avoid stack overflow)
Classic Recursive Problems
1. Fibonacci Sequence
code# Naive (exponential time) def fib(n): if n <= 1: return n return fib(n-1) + fib(n-2) # Optimized with memoization def fib_memo(n, memo={}): if n in memo: return memo[n] if n <= 1: return n memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo) return memo[n]
2. Power Function
codedef power(base, exp): if exp == 0: return 1 if exp == 1: return base # Even exponent: x^8 = (x^4)^2 if exp % 2 == 0: half = power(base, exp // 2) return half * half # Odd exponent: x^9 = x * x^8 return base * power(base, exp - 1) # O(log n) instead of O(n)!
3. Reverse a String
codedef reverse(s): if len(s) <= 1: return s return s[-1] + reverse(s[:-1]) print(reverse("hello")) # "olleh"
4. Sum of Digits
codedef sum_digits(n): if n == 0: return 0 return (n % 10) + sum_digits(n // 10) print(sum_digits(1234)) # 1+2+3+4 = 10
5. Binary Search (Recursive)
codedef binary_search(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(arr, target, left, mid - 1) else: return binary_search(arr, target, mid + 1, right)
Tree Recursion
Tree Traversal
codeclass TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None # Inorder: Left, Root, Right def inorder(root): if not root: return inorder(root.left) print(root.val) inorder(root.right) # Tree Height def height(root): if not root: return 0 return 1 + max(height(root.left), height(root.right)) # Count Nodes def count_nodes(root): if not root: return 0 return 1 + count_nodes(root.left) + count_nodes(root.right)
Backtracking
Definition: Systematically search all possible solutions by building them incrementally and abandoning ("backtracking") when they're invalid.
Template
codedef backtrack(candidate): if is_solution(candidate): output(candidate) return for next_choice in possible_choices(candidate): if is_valid(next_choice): make_choice(next_choice) backtrack(candidate + [next_choice]) unmake_choice(next_choice) # BACKTRACK!
Problem 1: Generate All Subsets
codedef subsets(nums): result = [] def backtrack(start, current): result.append(current[:]) for i in range(start, len(nums)): current.append(nums[i]) backtrack(i + 1, current) current.pop() # Backtrack backtrack(0, []) return result print(subsets([1,2,3])) # [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]
Problem 2: Permutations
codedef permutations(nums): result = [] def backtrack(current, remaining): if not remaining: result.append(current[:]) return for i in range(len(remaining)): current.append(remaining[i]) backtrack(current, remaining[:i] + remaining[i+1:]) current.pop() # Backtrack backtrack([], nums) return result print(permutations([1,2,3])) # [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
Problem 3: N-Queens
Place N queens on N×N chessboard so no queen attacks another.
codedef solve_n_queens(n): result = [] board = [['.'] * n for _ in range(n)] def is_safe(row, col): # Check column for i in range(row): if board[i][col] == 'Q': return False # Check diagonal (top-left) i, j = row - 1, col - 1 while i >= 0 and j >= 0: if board[i][j] == 'Q': return False i -= 1 j -= 1 # Check diagonal (top-right) i, j = row - 1, col + 1 while i >= 0 and j < n: if board[i][j] == 'Q': return False i -= 1 j += 1 return True def backtrack(row): if row == n: result.append([''.join(row) for row in board]) return for col in range(n): if is_safe(row, col): board[row][col] = 'Q' backtrack(row + 1) board[row][col] = '.' # Backtrack backtrack(0) return result
Problem 4: Sudoku Solver
codedef solve_sudoku(board): def is_valid(row, col, num): # Check row if num in board[row]: return False # Check column if num in [board[i][col] for i in range(9)]: return False # Check 3x3 box box_row, box_col = 3 * (row // 3), 3 * (col // 3) for i in range(box_row, box_row + 3): for j in range(box_col, box_col + 3): if board[i][j] == num: return False return True def backtrack(): for row in range(9): for col in range(9): if board[row][col] == '.': for num in '123456789': if is_valid(row, col, num): board[row][col] = num if backtrack(): return True board[row][col] = '.' # Backtrack return False return True backtrack() return board
Problem 5: Combination Sum
Find all combinations that sum to target.
codedef combination_sum(candidates, target): result = [] def backtrack(remaining, current, start): if remaining == 0: result.append(current[:]) return if remaining < 0: return for i in range(start, len(candidates)): current.append(candidates[i]) backtrack(remaining - candidates[i], current, i) current.pop() # Backtrack backtrack(target, [], 0) return result print(combination_sum([2,3,6,7], 7)) # [[2,2,3], [7]]
Common Backtracking Problems
- Subset problems: Generate all subsets
- Permutation problems: All arrangements
- Combination problems: Select k elements
- Partition problems: Split into groups
- Path problems: Find paths in grid/graph
- Constraint satisfaction: N-Queens, Sudoku
Optimization Tips
1. Pruning
Stop early when solution is impossible
2. Memoization
Cache results to avoid recomputation
3. Ordering
Try most promising options first
4. Iterative Deepening
Limit recursion depth, increase gradually
Avoiding Stack Overflow
codeimport sys sys.setrecursionlimit(10000) # Increase limit # OR convert to iteration using explicit stack def iterative_factorial(n): result = 1 for i in range(1, n + 1): result *= i return result
Practice Problems
- Generate all valid parentheses combinations
- Word search in grid
- Letter combinations of phone number
- Palindrome partitioning
- Restore IP addresses
- Combination sum with duplicates
- Generate all balanced BSTs