Recursion vs Backtracking – Complete Guide

🔹 1. Recursion Basics

Recursion = A function calling itself with a smaller subproblem until a base case is reached.

General template:

void recurse(params) {
    if (base case) return;   // stopping condition
    // work
    recurse(smaller problem);
}

---

🔹 2. Pass by Value vs Pass by Reference

• Java:

  • Primitives (int, char, double) → pass by value (a copy is passed).
  • Objects (ArrayList, HashMap) → reference is passed (so changes affect original).

• Python:

  • Everything is an object.
  • Mutable objects (list, dict, set) → changes persist across function calls.
  • Immutable objects (int, str, tuple) → new objects created instead of modifying.

---

🔹 3. Mutable vs Immutable

• Mutable: Can be changed after creation.
  Examples: Python list, dict; Java ArrayList, HashMap.

• Immutable: Cannot be changed after creation.
  Examples: Python int, str, tuple; Java String, Integer.

⚡ Why does this matter?
👉 Because backtracking is needed only when recursion modifies a mutable object.

---

🔹 4. When Do We Need Backtracking?

👉 Ask yourself:
Am I mutating a shared data structure?

• ✅ Yes (mutable, like list/array) → Backtracking needed

  • Pattern: add → recurse → remove
  • Shared object → undo is required.

• ❌ No (immutable, like string/number/new copy) → No backtracking

  • Each recursive call gets its own copy.
  • No undo required.

---

🔹 5. Immutable State Approach (No Backtracking)

Each recursive call gets a new snapshot of the state.

• Safe: no undo needed.
• Trade-off: more memory usage.

Example (Phone keypad combinations, immutable strings)

def pad(p, up):
    if not up:
        print(p)
        return
    digit = int(up[0])
    mapping = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
    for ch in mapping[digit]:
        pad(p + ch, up[1:])   # creates new string each call

Here p + ch creates a new string each time → no need to undo.

---

🔹 6. Mutable State Approach (Needs Backtracking)

Recursive calls share the same object.
We must undo changes after recursion to avoid corrupting results.

• Efficient: less memory usage.
• Risk: must backtrack properly.

Example (Phone keypad combinations, mutable list)

def letter_combinations(digits):
    mapping = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
    ans = []
    def solve(index, path):
        if index == len(digits):
            ans.append("".join(path))
            return
        for ch in mapping[int(digits[index])]:
            path.append(ch)           # add
            solve(index+1, path)
            path.pop()                # undo (backtrack)
    solve(0, [])
    return ans

Here path is shared → after exploring one branch, we pop() to reset it.

---

🔹 7. Rule of Thumb

• If using immutable state (string, int, tuple) → No backtracking.
• If using mutable state (list, array, dict, set) → Backtracking required.

---

🔹 8. Comparing Both Approaches

Approach	Example	Memory	Undo Needed?	When to Use
Immutable State	Passing p + ch in strings	High	❌ No	When input size is small / immutables are used
Mutable State	Modifying list with .append()	Low	✅ Yes	When input size is large / memory optimization needed

---

🔹 9. Example: Subset Problem

Without Backtracking (immutable list copies)

def subsets(nums):
    ans = []
    def dfs(index, path):
        if index == len(nums):
            ans.append(path[:])   # copy (new list)
            return
        dfs(index+1, path + [nums[index]])   # new list created
        dfs(index+1, path)                   # no change
    dfs(0, [])
    return ans

With Backtracking (mutable shared list)

def subsets(nums):
    ans = []
    def dfs(index, path):
        if index == len(nums):
            ans.append(path[:])   # copy final
            return
        path.append(nums[index])   # add
        dfs(index+1, path)
        path.pop()                 # undo
        dfs(index+1, path)
    dfs(0, [])
    return ans

---

🔹 10. Key Takeaways

1. Recursion = breaking problem into smaller subproblems.
2. Backtracking = recursion + undoing changes.
3. Check mutability:

• Immutable → no backtracking.

• Mutable → backtracking needed.

  1. Trade-off:

• Immutable → simpler, more memory.

• Mutable → efficient, needs careful undo.

---