Recursion & Backtracking

Recursion & Backtracking

Why This Matters

Recursion is a fundamental technique for working with tree and graph data structures. Many tree operations (traversal, search, manipulation) are naturally recursive because trees are recursive structures—each subtree is itself a tree. Understanding recursion is essential for implementing and understanding tree and graph algorithms.

This matters because recursive solutions are often simpler and more elegant than iterative ones for tree problems. A recursive tree traversal is 5-10 lines; an iterative version requires managing a stack manually and is 20-30 lines. Recursion also matches how we think about problems—solving a problem by solving smaller versions of the same problem.

In interviews, recursion questions test your ability to think recursively and work with recursive data structures. Interviewers want to know you can identify base cases, make recursive calls correctly, and understand the call stack. Real-world systems use recursion extensively—compilers use it for parsing (tree structures), file systems use it for directory traversal, and many algorithms are naturally recursive.

What Engineers Usually Get Wrong

Most engineers think "recursion is just a function calling itself." While true, the real insight is understanding the call stack—each recursive call creates a new stack frame, and the function doesn't return until all recursive calls complete. Engineers often forget base cases, causing infinite recursion and stack overflow.

Engineers also confuse recursion with iteration. They try to make everything iterative, missing that recursion is often simpler for tree problems. Or they use recursion when iteration would be better (like traversing a linked list, where iteration is simpler and more efficient).

Another common mistake is not understanding backtracking. Backtracking is recursion with undo operations—you make a choice, recurse, then undo the choice if it doesn't lead to a solution. Engineers forget to undo choices, causing incorrect results.

How This Breaks Systems in the Real World

A file system was traversing directories to find files. The engineer used recursion but didn't check for symbolic links that created cycles. When a symlink pointed back to an ancestor directory, the recursion entered an infinite loop, causing stack overflow and crashing the system. The fix? Track visited directories to detect cycles. The lesson? Recursion requires careful handling of edge cases, especially cycles in graphs.

Another story: A compiler was parsing code using recursive descent. The engineer didn't optimize tail recursion, and deeply nested expressions caused stack overflow. The fix? Use iterative parsing for certain constructs, or optimize tail recursion. The lesson? Deep recursion can cause stack overflow; understand when to use iteration instead.

Recursion Fundamentals

What is Recursion?

Recursion is when a function calls itself to solve a problem by breaking it into smaller subproblems of the same type.

Recursive Structure

Every recursive function has:

1. Base case: Condition that stops recursion (prevents infinite recursion)
2. Recursive case: Function calls itself with smaller input
3. Progress: Each recursive call moves toward base case

Example: Factorial

1function factorial(n: number): number {
2  // Base case: stop recursion
3  if (n <= 1) {
4    return 1;
5  }
6  
7  // Recursive case: solve smaller problem
8  return n * factorial(n - 1);
9}
10
11// Call stack for factorial(4):
12// factorial(4) → 4 * factorial(3)
13//   factorial(3) → 3 * factorial(2)
14//     factorial(2) → 2 * factorial(1)
15//       factorial(1) → 1 (base case)
16//     returns 2 * 1 = 2
17//   returns 3 * 2 = 6
18// returns 4 * 6 = 24
19
20// Time: O(n) - n recursive calls
21// Space: O(n) - call stack depth is n
22// Edge cases: n = 0, n < 0, stack overflow for large n

Recursion with Trees

Trees are naturally recursive—each subtree is itself a tree.

Tree Traversal (Recursive)

1class TreeNode {
2  val: number;
3  left: TreeNode | null;
4  right: TreeNode | null;
5  
6  constructor(val: number) {
7    this.val = val;
8    this.left = null;
9    this.right = null;
10  }
11}
12
13// Inorder traversal: Left, Root, Right
14function inorderTraversal(root: TreeNode | null): number[] {
15  const result: number[

Tree Search (Recursive)

1// Search in Binary Search Tree
2function searchBST(root: TreeNode | null, val: number): TreeNode | null {
3  // Base case: not found or empty tree
4  if (!root || root.val === val) {
5    return root;
6  }
7  
8  // Recursive case: search in appropriate subtree
9  if (val < root.val) {
10    return searchBST(root.left, val);   // Search left (smaller values)
11  } else {
12    return searchBST(root.right, val);

Backtracking

Backtracking is recursion with undo operations—you make a choice, recurse, then undo the choice if it doesn't lead to a solution.

Backtracking Template

1. Make a choice: Try one option
2. Recurse: Solve subproblem with this choice
3. Undo choice: If recursion doesn't find solution, undo and try next option

Example: Generate All Permutations

1function permute(nums: number[]): number[][] {
2  const result: number[][] = [];
3  const current: number[] = [];
4  const used: boolean[] = new Array(nums.length).fill(false);
5  
6  function backtrack(): void {
7    // Base case: found a complete permutation

Backtracking with Trees: Path Sum

1// Find all paths from root to leaf that sum to target
2function pathSum(root: TreeNode | null, targetSum: number): number[][] {
3  const result: number[][] = [];
4  const path: number[] = [];
5  
6  function backtrack(node: TreeNode | null, remaining: number): void {
7    // Base case: reached leaf
8    if (!node) return;

Call Stack and Recursion

How Call Stack Works

Each recursive call creates a new stack frame with:

• Function parameters
• Local variables
• Return address

When base case is reached, stack frames are popped in reverse order.

Visualizing Call Stack

factorial(3) call stack:
┌─────────────────┐
│ factorial(1)    │ ← Base case, returns 1
│ n = 1           │
└─────────────────┘
┌─────────────────┐
│ factorial(2)    │ ← Waits for factorial(1)
│ n = 2           │
└─────────────────┘
┌─────────────────┐
│ factorial(3)    │ ← Waits for factorial(2)
│ n = 3           │
└─────────────────┘

Stack Overflow

Deep recursion can exceed stack size limit (typically 1-8 MB).

Solution: Use iteration or tail recursion optimization.

Common Pitfalls

1. Missing base case: Causes infinite recursion and stack overflow
2. Not making progress: Recursive call doesn't move toward base case
3. Forgetting to undo: In backtracking, not undoing choices causes wrong results
4. Stack overflow: Deep recursion exceeds stack limit
5. Not handling null/empty: Tree/graph algorithms must handle empty structures

Failure Stories You'll Recognize

A file system was using recursion to traverse directories. The engineer didn't check for cycles (symlinks pointing to ancestors). When a symlink created a cycle, recursion entered an infinite loop, causing stack overflow and crashing the system. The fix? Track visited directories to detect cycles. The lesson? Recursion requires careful cycle detection in graphs.

Another story: A compiler was parsing deeply nested expressions using recursion. Expressions with 10,000 levels of nesting caused stack overflow. The fix? Use iterative parsing for certain constructs, or increase stack size. The lesson? Deep recursion can cause stack overflow; understand when to use iteration.

What Interviewers Are Really Testing

• Recursive thinking: Can you break problems into smaller subproblems?
• Base cases: Can you identify when recursion should stop?
• Tree algorithms: Can you implement tree operations recursively?
• Backtracking: Can you implement backtracking with proper undo?
• Optimization: Can you convert recursive to iterative when needed?

Interview Questions

Beginner

1. Implement recursive factorial
2. Traverse a binary tree recursively (inorder, preorder, postorder)
3. Find the height of a binary tree recursively

Intermediate

1. Generate all permutations using backtracking
2. Find all paths in a tree that sum to target
3. Implement recursive tree search and insertion

Senior

1. Convert recursive tree traversal to iterative
2. Optimize recursive solution using memoization
3. Design a backtracking solution for constraint satisfaction

1. Recursion matches tree structure: Trees are recursive, so recursive algorithms are natural
2. Base case is essential: Always define base case first to prevent infinite recursion
3. Call stack depth matters: Deep recursion can cause stack overflow
4. Backtracking requires undo: Must undo choices when backtracking
5. Recursion vs iteration: Recursion is simpler for trees, iteration for linear structures
6. Memoization optimizes: Cache results to avoid recomputing subproblems
7. Tail recursion: Can be optimized to iteration (saves stack space)
8. Graph algorithms: DFS is naturally recursive, BFS is iterative
9. Stack relationship: Recursion uses call stack, iteration uses explicit stack
10. Foundation for trees: Understanding recursion is essential for tree algorithms

• Trees - Recursive tree structures
• Graphs - Recursive graph traversal (DFS)
• Stacks - Call stack and explicit stacks
• Recursion - Deeper dive into recursion
• Backtracking - Advanced backtracking patterns