Introduction to Recursion & Backtracking

[!IMPORTANT] This chapter covers the 4 Pillars of Recursion: Intuition, Rigor, Hardware, and Patterns.

1. What is Recursion?

Recursion is solving a problem by breaking it down into smaller, self-similar sub-problems.

The Cinema Analogy

Imagine you are in a cinema. You ask the person in front of you, “Which row is this?” They don’t know, so they ask the person in front of them.

• Base Case: The person in Row 1 knows their row. They answer “Row 1”.
• Recursive Step: Each row adds 1 to the answer they received from the person in front.

---

2. Interactive: Call Stack Visualizer

Watch how functions pile up in memory (Push) and resolve (Pop).

Factorial(n):

---

3. Backtracking: Recursion + Undo

Backtracking is a technique for exploring all possibilities (Permutations, Combinations). The core idea: Choose → Explore → Undo.

The Blueprint

void backtrack(path, options) {
  if (goalReached) {
    res.add(new ArrayList<>(path)); // Found a solution!
    return;
  }
  for (option : options) {
    if (!isValid(option)) continue;
    path.add(option);        // 1. Choose
    backtrack(path, options); // 2. Explore
    path.remove(last);        // 3. Undo (Backtrack)
  }
}

---

4. Implementation: Permutations (Java & Go)

Java

private void backtrack(List<List<Integer>> res, List<Integer> path, int[] nums) {
  if (path.size() == nums.length) {
    res.add(new ArrayList<>(path));
    return;
  }
  for (int num : nums) {
    if (path.contains(num)) continue;
    path.add(num);
    backtrack(res, path, nums);
    path.remove(path.size() - 1);
  }
}

Go

func backtrack(path []int, nums []int, res *[][]int) {
  if len(path) == len(nums) {
    temp := make([]int, len(path))
    copy(temp, path)
    *res = append(*res, temp)
    return
  }
  for _, num := range nums {
    if contains(path, num) { continue }
    backtrack(append(path, num), nums, res)
  }
}

---

5. Summary & Complexity

• Time Complexity: Often O(N ċ N!) for permutations or O(2^N) for subsets.
• Space Complexity: O(N) for the recursion stack (or depth of search).
• Stack Overflow: Occurs if the base case is missing or recursion depth exceeds the stack limit.

---

6. Deep Dive Strategy Lab: Recursion Basics

Intuition Through Analogy

Think of this like finding your way through a maze. Every time you reach a fork (Decision), you pick a path. If you hit a wall (Failure), you walk back to the last fork and try the other direction (Backtrack).

Mathematical Anchor: The Master Theorem

Most recursive algorithms have time complexity that can be solved using: T(n) = aT(n/b) + f(n) This determines if the work at each level, the number of branches, or the depth of the tree dominates.