Recursion Patterns

Master Recursion Patterns for DSA + Competitive Programming

This guide helps you recognize recursion problems instantly using:

• input structure (array, tree, string, graph)
• recursion type (decision / generation / divide & conquer)
• keywords (subset, choice, path, split, return all, min/max)

Recursion becomes easy once you identify:

“What choices do I have at this step?” → “What smaller problem remains?”

---

Pattern Table (Simplified & High-Yield)

Pattern	Typical Question Types	Keywords / Detection Cues	Notes / When to Use
Decision Tree / Choice Recursion	Subsets, combinations, permutations	pick / not pick, choose, all possibilities	At each index, make a binary or multi-choice decision
Divide & Conquer	Split problem into halves	merge, sort, maximum, minimum	Break into subproblems, combine results (merge sort style)
Tree Recursion	Binary trees / N-ary trees	left, right, node, leaf, subtree	Each node naturally branches into recursive calls
DFS on Graph/Grid	Explore connected components	visited, island, path, flood fill	Recursion replaces stack; mark visited to avoid cycles
String Recursion	Substring generation, parsing	substring, partition, palindrome	Split string at every index or decision boundary
Optimization Recursion (Min/Max)	Best path, best cost	minimum, maximum, optimal, cost	Explore all paths, return best among recursive calls

---

1. Decision Tree / Choice Recursion (Most Important)

When to use / Detection cues:

• Input: array, string, list of items
• Keywords: subset, combination, permutation, pick/not pick
• Problem asks: “all possible ways”

Core idea: At each index → you have choices

• include element
• exclude element

Typical questions:

• Subsets of an array
• Combinations sum
• Permutations

Mental trigger: “Every element → take or skip” → Decision Tree recursion

---

2. Divide & Conquer (Split + Merge)

When to use / Detection cues:

• Problem can be split into equal halves
• Keywords: merge, sort, max/min range
• Input is array or numeric range

Core idea:

• Divide into smaller subproblems
• Solve recursively
• Combine results

Typical questions:

• Merge Sort
• Quick Sort
• Binary Search (recursive version)
• Maximum subarray (Kadane’s divide variant)

Mental trigger: “Split → Solve → Combine” → Divide & Conquer

---

3. Tree Recursion (Natural Recursion Structure)

When to use / Detection cues:

• Input: binary tree / N-ary tree
• Keywords: node, left, right, subtree

Core idea: Each node naturally calls:

• left child
• right child

Typical questions:

• Tree traversal (inorder, preorder, postorder)
• Height of tree
• Diameter of tree
• Lowest common ancestor

Mental trigger: “Node → left + right recursion” → Tree recursion

---

4. DFS on Graph/Grid (Traversal Recursion)

When to use / Detection cues:

• Input: matrix or graph
• Keywords: visited, island, connected, path
• Movement allowed in directions (up/down/left/right)

Core idea:

• Mark visited
• Explore neighbors recursively

Typical questions:

• Number of islands
• Flood fill
• Maze path existence
• Connected components

Mental trigger: “Explore all connected nodes” → DFS recursion

---

5. String Recursion (Split / Partition Problems)

When to use / Detection cues:

• Input: string
• Keywords: substring, partition, palindrome, split

Core idea: Try splitting string at every index and recurse on remaining part

Typical questions:

• Palindrome partitioning
• Generate all substrings
• Restore IP addresses
• Word break (recursive version)

Mental trigger: “Cut string at every position” → String recursion

---

6. Optimization Recursion (Min / Max Problems)

When to use / Detection cues:

• Keywords: minimum, maximum, best, optimal
• Multiple recursive paths exist
• Need best result among all choices

Core idea:

• Explore all possibilities
• Return best value using min/max

Typical questions:

• Minimum path sum
• Maximum profit path
• Coin change (recursive version)
• Knapsack (recursive version)

Mental trigger: “Try all paths → pick best” → Optimization recursion

---

Mini Notes / Tips

### Recursion Master Rules

- Every recursion has 3 parts:
  1. Base case (stop condition)
  2. Choice (what decisions exist?)
  3. Recursive call (smaller problem)

- If you see "all possible ways" → Decision Tree
- If input is a tree → natural recursion
- If grid/matrix → DFS recursion
- If array split → Divide & Conquer
- If best/min/max → Optimization recursion
- If string → think split at every index

### Golden Thinking Pattern

STATE → CHOICES → RECURSE → COMBINE → RESULT