Recap — Recursion and Backtracking Templates

# Recursion and Backtracking Templates Recursion: a function that calls itself with a smaller version of the problem. Backtracking: recursion that explores choices and undoes them. Together they solve a huge class of interview problems. ## The recursion template ```python def recurse(state): # 1. Base case: when to stop if base_condition(state): return base_result # 2. Recursive case: smaller subproblem(s) return combine(recurse(smaller_state), ...) ``` Two questions to answer: 1. **What's the base case?** When is the problem trivial? 2. **How does the problem shrink?** What's the smaller version? ### Example: Factorial ```python def factorial(n): if n <= 1: # base case return 1 return n * factorial(n - 1) # smaller subproblem ``` ### Example: Sum of list ```python def list_sum(arr, i=0): if i == len(arr): # base case return 0 return arr[i] + list_sum(arr, i + 1) ``` Pass index, not slice — avoid O(N²) copying. ## When to use recursion - **Tree/graph traversal** — natural fit. - **Divide and conquer** — merge sort, quicksort, binary search. - **Generate all X** — subsets, permutations, combinations. - **Reductive problem** — solve N-1 to solve N (DP candidate). When NOT: - Simple iteration would do (don't over-engineer). - Stack depth might exceed limit (Python default is ~1000). - Recursion has overlapping subproblems → memoize or iterate. ## Backtracking template Backtracking = recursion + explore choices + undo. ```python def backtrack(state, choices): if is_solution(state): results.append(copy(state)) return for choice in choices: if is_valid(choice, state): apply(choice, state) backtrack(state, remaining_choices) undo(choice, state) # the "backtrack" ``` ### Example: Generate all subsets ```python def subsets(nums): result = [] def backtrack(start, path): result.append(list(path)) # every state is a subset for i in range(start, len(nums)): path.append(nums[i]) # choose backtrack(i + 1, path) # explore path.pop() # undo backtrack(0, []) return result ``` ### Example: Generate all permutations ```python def permutations(nums): result = [] def backtrack(path, remaining): if not remaining: result.append(list(path)) return for i in range(len(remaining)): path.append(remaining[i]) backtrack(path, remaining[:i] + remaining[i+1:]) path.pop() backtrack([], nums) return result ``` ### Example: N-Queens ```python def n_queens(n): result = [] cols = set(); diag1 = set(); diag2 = set() def backtrack(row, board): if row == n: result.append(board[:]) return for col in range(n): if col in cols or (row - col) in diag1 or (row + col) in diag2: continue cols.add(col); diag1.add(row - col); diag2.add(row + col) board.append(col) backtrack(row + 1, board) board.pop() cols.remove(col); diag1.remove(row - col); diag2.remove(row + col) backtrack(0, []) return result ``` Note the pattern: choose, explore, undo. The "undo" is what makes it backtracking. ## Complexity of backtracking Usually exponential. For subsets: O(2ᴺ × N). For permutations: O(N! × N). That's fine when N is small (~20). Backtracking is the right answer when the problem says "generate all" or "count all" or "find any". ## How to think recursively (the mental shift) Don't trace the recursion in your head. Instead: 1. **Trust the recursive call.** Assume `recurse(smaller)` works correctly. 2. **Combine its result with current work.** Add, concatenate, max, etc. 3. **Define the base case.** Smallest valid input. ```python def reverse(s): if len(s) <= 1: return s # base: trust nothing or single char return reverse(s[1:]) + s[0] # trust that reverse(s[1:]) works ``` Don't trace. Trust. ## Common recursion mistakes 1. **Forgetting base case.** Stack overflow. 2. **Wrong base case.** Doesn't handle edge inputs (empty list, n=0). 3. **Modifying shared state in recursion without undoing.** Inconsistent results. 4. **Returning vs appending.** Decide: function returns the result, OR mutates a shared accumulator. Don't mix. 5. **Copying paths/state when needed.** `result.append(path)` stores a reference; future mutations corrupt it. Use `result.append(list(path))` or `path.copy()`. ## Tail recursion in Python Python doesn't optimize tail calls. A deep recursion (>1000) blows the stack. Either iterate or `sys.setrecursionlimit(10000)`. For interview problems, recursion depth is usually fine, but mention it as a trade-off in code review discussions. ## Takeaway Recursion = self-call with smaller input + base case. Backtracking = recursion + choose/explor