Recursion Patterns

1. Introduction: The Recursive Arsenal

Basic recursion (like Factorial or Fibonacci) is just a warm-up. In real FAANG interviews, recursion is never the final answer—it is a tool used to implement massive algorithmic strategies.

You need to recognize three primary recursive patterns:

1. Divide and Conquer: Break a problem into completely independent halves, solve them recursively, and merge them. (e.g., Merge Sort, Binary Search).
2. Subsets / Combinatorics: Generate all possible groupings by exploring two parallel realities: one where you include an item, and one where you don't.
3. Backtracking (Preview): Systematically build a solution piece by piece, and the moment a rule is violated, undo your last step and try a different path.

2. Core Pattern 1: Divide and Conquer

This pattern cuts the input size in half at every step. This leads to blazing-fast $O(\log N)$ or $O(N \log N)$ time complexities.

Problem Statement: (LeetCode 108) Convert Sorted Array to Binary Search Tree. Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced BST.

The Insight: The root of a balanced BST MUST be the exact middle element of the sorted array! Once you pick the middle, everything to its left goes into the left subtree, and everything to its right goes into the right subtree.

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class SortedArrayToBST {
    public TreeNode sortedArrayToBST(int[] nums) {
        return buildTree(nums, 0, nums.length - 1);
    }
    
    private TreeNode buildTree(int[] nums, int left, int right) {
        // Base Case: Invalid range (we ran out of elements)
        if (left > right) {
            return null;
        }
        
        // 1. DIVIDE: Find the middle
        int mid = left + (right - left) / 2;
        
        // 2. CONQUER: Create the root node
        TreeNode node = new TreeNode(nums[mid]);
        
        // 3. RECURSE: Build the left and right halves independently
        node.left = buildTree(nums, left, mid - 1);
        node.right = buildTree(nums, mid + 1, right);
        
        return node;
    }
}

3. Core Pattern 2: The Include/Exclude Branching (Subsets)

When a problem asks for "all possible ways" to group elements, you must use a specific recursive branching pattern. At every index, you branch into two universes: Universe A includes the current element. Universe B excludes the current element.

Problem Statement: (LeetCode 78) Subsets. Given an integer array nums of unique elements, return all possible subsets (the power set).

The Insight: If the array is [1, 2]. At index 0, we can either take 1 or ignore it. At index 1, we can either take 2 or ignore it. The leaves of this recursive tree perfectly represent all 4 subsets: [], [1], [2], [1,2].

import java.util.ArrayList;
import java.util.List;

public class SubsetsPattern {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        generateSubsets(0, nums, new ArrayList<>(), result);
        return result;
    }
    
    private void generateSubsets(int index, int[] nums, List<Integer> current, List<List<Integer>> result) {
        // Base Case: We made a decision for every element
        if (index == nums.length) {
            // Must make a DEEP COPY of the current list!
            result.add(new ArrayList<>(current));
            return;
        }
        
        // Universe A: EXCLUDE the current element
        // We just move to the next index without changing 'current'
        generateSubsets(index + 1, nums, current, result);
        
        // Universe B: INCLUDE the current element
        current.add(nums[index]); // Add it
        generateSubsets(index + 1, nums, current, result); // Recurse
        
        // BACKTRACK: Remove the element so the parent function 
        // can reuse the 'current' list for other branches!
        current.remove(current.size() - 1);
    }
}

Note: This specific pattern is the foundational bridge into Backtracking and DP Knapsack problems.

4. Core Pattern 3: Top-Down Recursion with Memoization

Basic branching recursion (like Fibonacci) calculates the exact same state millions of times. We can eliminate this duplicate work by caching the results in a HashMap or Array.

Problem Statement: (LeetCode 70) Climbing Stairs. You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

The Insight: To get to step N, you MUST have come from either step N-1 or step N-2. Therefore, ways(N) = ways(N-1) + ways(N-2). Sound familiar? It's Fibonacci! But we must memoize it.

public class ClimbingStairs {
    public int climbStairs(int n) {
        // Cache array. Default values are 0.
        int[] memo = new int[n + 1];
        return dp(n, memo);
    }
    
    private int dp(int i, int[] memo) {
        // Base cases
        if (i <= 1) return 1;
        
        // Cache Check: If we already calculated this step, return it instantly!
        if (memo[i] != 0) {
            return memo[i];
        }
        
        // Recursive calculation
        int ways = dp(i - 1, memo) + dp(i - 2, memo);
        
        // Cache Assignment: Save it for future recursive branches
        memo[i] = ways;
        
        return ways;
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$ because each step is calculated exactly once.
• Space Complexity: $O(N)$ for the recursion stack and memoization array.

5. Common Mistakes Beginners Make

1. Not Deep Copying the output in Subsets/Backtracking

   • The Mistake: result.add(current);
   • Why it's wrong: current is a reference to a single ArrayList in memory. If you add the reference, and then remove() elements from it later in the recursion, the item inside result will also be modified! You will end up with a massive list of empty arrays: [[], [], [], []].
   • The Fix: ALWAYS result.add(new ArrayList<>(current));.

2. Accidentally mutating state for parallel branches

   • The Mistake:

   current.add(nums[index]);
   generateSubsets(index + 1, nums, current, result); 
   // Forgot to remove it!
   

   • Why it's wrong: The current list is passed down the call stack. If the right branch adds an element and doesn't clean up after itself, when the call stack unwinds and the left branch resumes, the left branch will contain garbage data from the right branch!

3. Returning inside a void function

   • The Mistake: Thinking return; inside a void recursive function ends the whole algorithm.
   • Why it's wrong: return; only kills the current stack frame. The parent function will immediately resume execution. To kill the entire algorithm (e.g., you found a target and want to stop searching), you must return a boolean and check if (recurse()) return true;.

6. Interview Q&A

Q1: What's the difference between Divide & Conquer and Dynamic Programming? Answer: Both use recursion to break problems into smaller pieces. However, Divide & Conquer splits the problem into independent non-overlapping pieces (like splitting an array in half for Merge Sort). DP splits problems into overlapping subproblems (like Fibonacci, where both branches need to calculate F(3)). That's why DP requires Memoization (caching), while Divide & Conquer does not.

Q2: What is the maximum depth a Java recursion stack can handle? Answer: The default JVM stack size usually handles around 10,000 recursive calls before throwing a StackOverflowError. If you expect $N=10^5$, you must convert your recursion into iteration.

Q3: Can Memoization use HashMaps instead of Arrays? Answer: Yes! If the recursive state is a single index, an array is faster. But if the recursive state involves multiple variables (like an index AND a remaining weight capacity), you can concatenate them into a String key "index,weight" and use a Map<String, Integer>.

7. Practice Problems

1. Convert Sorted Array to Binary Search Tree (LeetCode 108)
   • Goal: Master the Divide and Conquer mid-point logic.
2. Subsets (LeetCode 78)
   • Goal: Master the Include/Exclude branching logic and deep copying.
3. Climbing Stairs (LeetCode 70)
   • Goal: Master Top-Down Memoization.

8. Summary

• Divide and Conquer: mid = left + right / 2. Send the left half to recurse(left, mid) and right half to recurse(mid+1, right).
• Include/Exclude: Generate all combinations by explicitly calling the function twice: once passing the state with the item, once without the item.
• Deep Copy: Never append a shared mutable object (like a List) directly to an output result.
• Memoization: The ultimate cheat code to drop $O(2^N)$ algorithms to $O(N)$.