Ai-CompTech

AI Computing

Computer Science Fundamentals

Recursion and Backtracking

Master recursive thinking and backtracking algorithms

Advanced 75 min read 0 examples 0 quiz questionsID: 6962f8e8
Lesson Content

Recursion and Backtracking

What is Recursion?

A function that calls itself to solve smaller versions of the same problem.

Key Components

  1. Base Case: When to stop recursing
  2. Recursive Case: How to break down the problem
  3. Progress: Each call moves toward base case

Simple Example: Factorial

code
def 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

code
def countdown(n): if n == 0: print("Blastoff!") else: print(n) countdown(n - 1) countdown(3)

Call Stack:

code
countdown(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

code
def recursive_sum(arr): if len(arr) == 0: return 0 return arr[0] + recursive_sum(arr[1:])

Iterative Sum

code
def 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

code
def 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

code
def reverse(s): if len(s) <= 1: return s return s[-1] + reverse(s[:-1]) print(reverse("hello")) # "olleh"

4. Sum of Digits

code
def 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)

code
def 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

code
class 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

code
def 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

code
def 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

code
def 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.

code
def 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

code
def 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.

code
def 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

  1. Subset problems: Generate all subsets
  2. Permutation problems: All arrangements
  3. Combination problems: Select k elements
  4. Partition problems: Split into groups
  5. Path problems: Find paths in grid/graph
  6. 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

code
import 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

  1. Generate all valid parentheses combinations
  2. Word search in grid
  3. Letter combinations of phone number
  4. Palindrome partitioning
  5. Restore IP addresses
  6. Combination sum with duplicates
  7. Generate all balanced BSTs