Data Structures & AlgorithmsDivide and Conquer

The D&C Pattern — Divide, Conquer, Combine

LevelIntermediate

Duration75 mins

TopicDivide and Conquer

4 / 4

Recursive Structure

The Recursive Heart of D&C

Divide and Conquer and recursion are inseparable. The very definition of D&C—solve a problem by solving smaller instances of the same problem—is the essence of recursive thinking. When you write a D&C algorithm, you're writing a recursive algorithm. When you analyze a D&C algorithm, you're analyzing recursive call patterns. But recursion in D&C is more than just "a function that calls itself." The recursive structure of D&C algorithms has specific characteristics that enable both correctness reasoning and performance analysis. Understanding this structure deeply is essential for: Designing new D&C solutions from scratch Debugging when D&C algorithms behave unexpectedly Optimizing by understanding stack depth and call patterns Analyzing complexity using recurrence relations Converting between recursive and iterative implementations when needed In this page, we'll explore the recursive structure of D&C comprehensively, building from fundamental concepts to advanced optimization techniques.

What You Will Learn

This page covers: why recursion naturally expresses D&C, the recursion tree model for visualizing D&C execution, reasoning about recursive correctness using induction, stack space analysis and management, and the relationship between recursive D&C and iterative alternatives.

Why Recursion is Natural for D&C

The connection between D&C and recursion isn't coincidental—it's definitional. D&C is fundamentally a recursive paradigm. The Structural Match: Consider the D&C pattern: solve(problem) = if problem is small enough: return direct_solution(problem) else: subproblems = divide(problem) subsolutions = [solve(subproblem) for subproblem in subproblems] return combine(subsolutions) This is recursion: solve calls solve on smaller inputs. The recursion terminates because: Each recursive call receives a strictly smaller problem Eventually, problems become small enough to hit the base case Base cases return without further recursion Why Recursion Fits D&C: Self-similarity : D&C exploits the fact that subproblems have the same structure as the original problem. Recursion is the programming construct that captures self-similarity. Automatic state management : Each recursive call gets its own stack frame with its own local variables. This naturally isolates each subproblem's state. Implicit work tracking : The call stack naturally tracks which subproblems are pending and in what order they'll be combined. Correctness reasoning : Recursive structure enables inductive correctness proofs—assume the function works for smaller inputs, prove it works for the current input.

Recursion in Action: D&C Algorithms
Algorithm	Recursive Call Pattern	What Recursion Manages
Merge Sort	Two calls on each half	Sorting state for each subarray
Binary Search	One call on selected half	Search range boundaries
Quick Sort	Two calls on partitions	Partition boundaries, pivot positions
Tree Traversal	Calls on left and right subtrees	Current position in tree
Closest Pair	Two calls on point subsets	Subset boundaries, minimum distances
Strassen's	Seven calls on submatrices	Submatrix positions and intermediate products

The Alternative View

While D&C is naturally recursive, some D&C algorithms can be expressed iteratively using explicit stacks or queues. However, iterative versions are usually harder to read and reason about. Recursion is the clearer expression of D&C logic, and compilers often optimize recursive calls well.

The Recursion Tree Model

The recursion tree is a powerful mental model for understanding D&C algorithms. It's a tree where: Each node represents a subproblem (a single invocation of the D&C function) The root is the original problem Children of a node are the subproblems it divides into Leaves are base cases (no further children) The work at each node is the cost of divide + combine for that subproblem Visualizing Merge Sort's Recursion Tree: Level 0: [n elements] Work: O(n) merge / Level 1: [n/2] [n/2] Work: 2 × O(n/2) = O(n) / \ / Level 2: [n/4][n/4][n/4][n/4] Work: 4 × O(n/4) = O(n) ... ... ... ... Level log(n): [1][1][1][1]...[1][1] Work: n × O(1) = O(n) Insights from the Recursion Tree: Height = O(log n) for algorithms that halve problem size Width increases with depth (more subproblems at deeper levels) Total work = sum of work across all levels When each level does O(n) work and there are O(log n) levels, total = O(n log n)

recursion_tree_visualization.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
# Visualizing recursion trees
 
def visualize_merge_sort_tree(n, level=0, label="root"):
    """
    Prints the recursion tree for Merge Sort.
    Shows how the problem divides at each level.
    """
    indent = "  " * level
    work_at_node = n  # Merge operation costs O(n)
    
    print(f"{indent}[{label}] size={n}, merge_cost={work_at_node}")
    
    if n <= 1:
        print(f"{indent}  (base case)")
        return work_at_node
    
    mid = n // 2
    
    # Recursive calls
    left_work = visualize_merge_sort_tree(mid, level + 1, "L")
    right_work = visualize_merge_sort_tree(n - mid, level + 1, "R")
    
    return work_at_node + left_work + right_work
 
 
def visualize_binary_search_tree(n, level=0, target_side="both"):
    """
    Visualize Binary Search recursion tree.
    Note: Only ONE branch is taken at each level (unlike Merge Sort).
    """
    indent = "  " * level
    work_at_node = 1  # O(1) comparison
    
    print(f"{indent}[search in size={n}] cost={work_at_node}")
    
    if n <= 1:
        print(f"{indent}  (base: found or not in empty range)")
        return work_at_node
    
    # In Binary Search, we only go ONE direction (simulating 50% chance each way)
    mid = n // 2
    
    if target_side == "left":
        return work_at_node + visualize_binary_search_tree(mid, level + 1, "left")
    else:
        return work_at_node + visualize_binary_search_tree(n - mid - 1, level + 1, "right")
 
 
def analyze_recursion_tree(n, branching_factor, size_divisor, work_per_node):
    """
    General analysis of a D&C recursion tree.
    
    Parameters:
    - n: problem size
    - branching_factor (a): number of subproblems at each node
    - size_divisor (b): each subproblem is size n/b
    - work_per_node: function that computes work at node given size
    
    Returns total work done.
    """
    if n < 1:
        return 0
    
    # Work at this node
    node_work = work_per_node(n)
    
    if n == 1:
        return node_work
    
    # Recursive: 'branching_factor' children, each with size n/size_divisor
    child_work = 0
    subproblem_size = max(1, n // size_divisor)
    for _ in range(branching_factor):
        child_work += analyze_recursion_tree(
            subproblem_size, branching_factor, size_divisor, work_per_node
        )
    
    return node_work + child_work
 
 
# Examples
print("=== Merge Sort Recursion Tree (n=8) ===")
total = visualize_merge_sort_tree(8)
print(f"Total work: {total}")
 
print()
print("=== Binary Search Recursion Tree (n=16) ===")
total = visualize_binary_search_tree(16, target_side="right")
print(f"Total work: {total}")
 
print()
print("=== General D&C Analysis ===")
 
# Merge Sort: a=2, b=2, f(n)=n  → Total O(n log n)
print(f"Merge Sort (n=1000): {analyze_recursion_tree(1000, 2, 2, lambda n: n)}")
 
# Binary Search: a=1, b=2, f(n)=1  → Total O(log n)
print(f"Binary Search (n=1000): {analyze_recursion_tree(1000, 1, 2, lambda n: 1)}")

Key Recursion Tree Patterns:

Pattern	Branching	Per-Level Work	Total Complexity
Linear (Binary Search)	1	O(1)	O(log n)
Balanced (Merge Sort)	2, halving	O(n) per level	O(n log n)
Heavy leaves (many small)	2, halving	O(1) per node	O(n)
Heavy root	2, halving	O(n²) per node	O(n²)
Strassen's	7, halving	O(n²)	O(n^2.81)

The Master Theorem formalizes these patterns, but the recursion tree gives intuition for why the formulas work.

Reasoning about Recursive Correctness

How do you know a recursive D&C algorithm is correct? The answer lies in mathematical induction, which maps perfectly onto recursive structure. The Inductive Correctness Argument: To prove a recursive D&C algorithm correct: Base Case : Prove the algorithm is correct for the smallest input(s) that hit the base case. Inductive Hypothesis : Assume the algorithm is correct for all inputs smaller than size n. Inductive Step : Prove that if the algorithm correctly solves subproblems (by the inductive hypothesis), and the combine step correctly synthesizes subsolutions, then the algorithm is correct for size n. This exactly mirrors the structure of D&C: Base case in the algorithm \leftrightarrow Base case in the proof Recursive calls returning correct results \leftrightarrow Inductive hypothesis Combine producing correct result from subsolutions \leftrightarrow Inductive step

correctness_proof.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
# Example: Proving Merge Sort correctness by induction
 
def merge_sort(arr):
    """
    Merge Sort with inline correctness annotations.
    
    CORRECTNESS CLAIM: merge_sort(arr) returns a sorted permutation of arr.
    """
    # BASE CASE
    if len(arr) <= 1:
        # PROOF: An array of length 0 or 1 is trivially sorted.
        # It's also trivially a permutation of itself.
        return arr[:]
    
    mid = len(arr) // 2
    
    # INDUCTIVE HYPOTHESIS (for recursive calls):
    # Assume merge_sort correctly returns sorted permutations for smaller arrays.
    
    left = merge_sort(arr[:mid])
    # By IH: left is a sorted permutation of arr[:mid]
    
    right = merge_sort(arr[mid:])
    # By IH: right is a sorted permutation of arr[mid:]
    
    # INDUCTIVE STEP: Prove merge produces correct result
    result = merge(left, right)
    # Claim: result is a sorted permutation of arr
    
    # Proof sketch:
    # 1. left contains exactly arr[:mid]'s elements (by IH, it's a permutation)
    # 2. right contains exactly arr[mid:]'s elements (by IH)
    # 3. merge combines ALL elements from left and right (see merge implementation)
    # 4. Therefore result contains exactly arr's elements: it's a permutation ✓
    # 5. merge compares and selects smallest available elements in order
    # 6. Since left and right are each sorted, and we always take the smaller,
    #    result is sorted ✓
    
    return result
 
 
def merge(left, right):
    """
    Merge two sorted arrays into one sorted array.
    
    PRECONDITION: left and right are sorted.
    POSTCONDITION: returns sorted array containing all elements of left and right.
    """
    result = []
    i = j = 0
    
    # LOOP INVARIANT:
    # - result contains the i smallest elements of left and j smallest of right
    # - result is sorted
    # - all elements in result are smaller than left[i] and right[j]
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            # left[i] is smallest remaining element
            result.append(left[i])
            i += 1
        else:
            # right[j] is smallest remaining element
            result.append(right[j])
            j += 1
    
    # At most one of these runs (the other is exhausted)
    result.extend(left[i:])
    result.extend(right[j:])
    
    # POSTCONDITION: result contains all elements, sorted ✓
    return result
 
 
# The beauty of this proof structure:
# We only need to verify:
# 1. Base case returns correct result (trivial)
# 2. merge is correct given sorted inputs (local reasoning)
# 
# We DON'T need to trace through the entire recursion tree!
# The induction handles all levels automatically.

Trust the Recursion

The inductive approach teaches us to TRUST that recursive calls return correct results. When writing D&C, don't try to trace through what the recursive call does internally. Simply assume it works for smaller inputs, and focus on whether your divide and combine logic is correct given that assumption.

Stack Space and Memory Considerations

Every recursive call consumes stack space. Understanding stack usage is crucial for D&C algorithms, especially with large inputs. How Recursion Uses Stack: Each recursive call pushes: Return address (where to continue after the call returns) Parameters passed to the function Local variables Saved registers This stack frame remains until the call returns. In D&C: The maximum stack depth equals the maximum recursion depth For algorithms that halve problem size, depth = O(log n) For unbalanced recursion, depth can be O(n) Stack Space Analysis:

Algorithm	Recursion Depth	Stack Space	Notes
Merge Sort	O(log n)	O(log n)	Balanced halving
Binary Search	O(log n)	O(log n)	Single recursive call
Quick Sort (balanced)	O(log n)	O(log n)	When pivots split evenly
Quick Sort (worst)	O(n)	O(n)	When pivots always at edge
Clever Quick Sort	O(log n)	O(log n)	Tail recursion on larger half

stack_space_analysis.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
import sys
 
# Demonstrate stack depth in D&C algorithms
 
def merge_sort_with_depth_tracking(arr, depth=0):
    """
    Merge Sort that tracks maximum recursion depth.
    """
    global max_depth
    max_depth = max(max_depth, depth)
    
    if len(arr) <= 1:
        return arr[:]
    
    mid = len(arr) // 2
    left = merge_sort_with_depth_tracking(arr[:mid], depth + 1)
    right = merge_sort_with_depth_tracking(arr[mid:], depth + 1)
    
    return merge(left, right)
 
 
def quick_sort_worst_case(arr, depth=0):
    """
    Quick Sort with worst-case pivot selection (always first element).
    Demonstrates O(n) stack depth on sorted input.
    """
    global max_depth
    max_depth = max(max_depth, depth)
    
    if len(arr) <= 1:
        return arr[:]
    
    pivot = arr[0]  # Always pick first - bad for sorted input!
    left = [x for x in arr[1:] if x < pivot]
    right = [x for x in arr[1:] if x >= pivot]
    
    # Two recursive calls - both contribute to depth
    return quick_sort_worst_case(left, depth + 1) + [pivot] + quick_sort_worst_case(right, depth + 1)
 
 
def quick_sort_tail_optimized(arr, depth=0):
    """
    Quick Sort with tail call optimization:
    Always recurse on smaller partition first, then iterate on larger.
    This limits stack depth to O(log n).
    """
    global max_depth
    
    while len(arr) > 1:
        max_depth = max(max_depth, depth)
        
        # Partition
        pivot = arr[len(arr) // 2]  # Better pivot choice
        left = [x for x in arr if x < pivot]
        middle = [x for x in arr if x == pivot]
        right = [x for x in arr if x > pivot]
        
        # Recurse on SMALLER partition, iterate on larger
        if len(left) < len(right):
            sorted_left = quick_sort_tail_optimized(left, depth + 1)
            arr = right  # Iterate on right (larger)
            result_prefix = sorted_left + middle
        else:
            sorted_right = quick_sort_tail_optimized(right, depth + 1)
            arr = left  # Iterate on left (larger)
            result_suffix = middle + sorted_right
    
    # Handle base case
    if len(arr) <= 1:
        if 'result_prefix' in dir():
            return result_prefix + arr + (result_suffix if 'result_suffix' in dir() else [])
        return arr
    
    return arr
 
 
def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result
 
 
# Test stack depths
import random
 
for size in [100, 1000, 10000]:
    # Merge Sort - always O(log n) depth
    max_depth = 0
    arr = [random.randint(0, 1000) for _ in range(size)]
    merge_sort_with_depth_tracking(arr)
    print(f"Merge Sort n={size}: max depth = {max_depth}, log₂(n) ≈ {size.bit_length()}")
 
print()
 
# Quick Sort worst case - O(n) depth on sorted input
# Warning: May cause stack overflow for large n!
for size in [100, 500, 1000]:
    max_depth = 0
    arr = list(range(size))  # Already sorted - worst case for naive Quick Sort
    try:
        sys.setrecursionlimit(size + 100)
        quick_sort_worst_case(arr)
        print(f"Quick Sort (worst) n={size}: max depth = {max_depth}")
    except RecursionError:
        print(f"Quick Sort (worst) n={size}: STACK OVERFLOW!")

Stack Overflow Risk

For very large inputs (millions of elements) or unbalanced recursion, stack overflow is a real risk. Most systems have stack limits of 1-8 MB. With ~100 bytes per frame, that's 10,000-80,000 maximum depth. O(n) depth algorithms can overflow; O(log n) depth algorithms are safe.

Mitigating Stack Space Issues: Tail Recursion Optimization : Recurse on the smaller subproblem, iterate (loop) on the larger. This limits depth to O(log n) even for Quick Sort. Iterative Conversion : Convert recursion to iteration using an explicit stack data structure. You control stack size. Hybrid Approaches : Switch to a non-recursive algorithm for small subproblems (like using Insertion Sort for small subarrays in Merge Sort). Increase Stack Limit : Some languages allow increasing the stack size (Python's sys.setrecursionlimit, compiler flags for C++).

Anatomy of a D&C Recursive Call

Let's dissect exactly what happens during a D&C recursive call, step by step. The Life of a D&C Call: CALLER: solve(problem_n) │ ├─\to CHECK: Is this a base case? │ │ │ ├─ YES: Return direct solution, pop stack frame │ │ │ └─ NO: Continue to divide │ ├─\to DIVIDE: Split into subproblems │ ├─\to RECURSE #1: solve(subproblem_1) │ │ │ └─ (new stack frame, entire process repeats for subproblem_1) │ │ │ └─\to Returns subsolution_1 │ ├─\to RECURSE #2: solve(subproblem_2) │ │ │ └─ (new stack frame, entire process repeats for subproblem_2) │ │ │ └─\to Returns subsolution_2 │ ├─\to COMBINE: Merge subsolution_1 and subsolution_2 │ └─\to RETURN: combined solution to CALLER

anatomy_of_dc_call.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
# Detailed trace of a D&C call
 
call_id = 0
 
def merge_sort_traced(arr, depth=0):
    """
    Merge Sort with detailed tracing of call lifecycle.
    """
    global call_id
    my_id = call_id
    call_id += 1
    
    indent = "  " * depth
    
    # ENTRY: New call begins
    print(f"{indent}[CALL {my_id}] ENTER: arr={arr}")
    
    # STEP 1: Base case check
    if len(arr) <= 1:
        print(f"{indent}[CALL {my_id}] BASE CASE: returning {arr}")
        return arr[:]
    
    # STEP 2: Divide
    mid = len(arr) // 2
    left_arr = arr[:mid]
    right_arr = arr[mid:]
    print(f"{indent}[CALL {my_id}] DIVIDE: left={left_arr}, right={right_arr}")
    
    # STEP 3a: First recursive call (blocks until complete)
    print(f"{indent}[CALL {my_id}] RECURSE LEFT...")
    left_sorted = merge_sort_traced(left_arr, depth + 1)
    print(f"{indent}[CALL {my_id}] LEFT RETURNED: {left_sorted}")
    
    # STEP 3b: Second recursive call (blocks until complete)
    print(f"{indent}[CALL {my_id}] RECURSE RIGHT...")
    right_sorted = merge_sort_traced(right_arr, depth + 1)
    print(f"{indent}[CALL {my_id}] RIGHT RETURNED: {right_sorted}")
    
    # STEP 4: Combine
    print(f"{indent}[CALL {my_id}] COMBINE: merging {left_sorted} and {right_sorted}")
    result = merge(left_sorted, right_sorted)
    
    # STEP 5: Return
    print(f"{indent}[CALL {my_id}] EXIT: returning {result}")
    return result
 
 
def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result
 
 
# Trace a small example
print("=== MERGE SORT TRACED ===")
call_id = 0
result = merge_sort_traced([3, 1, 4, 2])
print(f"
FINAL RESULT: {result}")
 
# Output shows the complete lifecycle:
# - How calls nest within each other
# - How base cases terminate branches
# - How results bubble up through the combine steps
# - The order of operations (preorder: divide before recursing, 
#                          postorder: combine after returning)

Key Observations: Blocking calls : Each recursive call blocks the caller until it completes. The caller waits for subsolutions before it can combine. Stack unwinding : Solutions bubble up from leaves (base cases) to root. The root's combine step happens last. Order of operations : Divide happens in preorder (before any recursive calls) Combine happens in postorder (after all recursive calls return) This is like a reverse tree traversal: visit children before processing parent Independence in action : While one recursive call is active, others haven't started yet (in sequential execution). This is why independence matters—each call doesn't need results from sibling calls, only from its children.

Iterative Alternatives to Recursion

While recursion naturally expresses D&C, iterative implementations are sometimes necessary or desirable—for performance, stack limitations, or language constraints. Converting Recursion to Iteration: Every recursive algorithm can be converted to iteration using an explicit stack. The stack simulates what the call stack does automatically: Push the initial problem onto the stack Pop a problem from the stack If base case, record solution; otherwise divide and push subproblems Repeat until stack is empty Combine solutions in appropriate order The challenge is managing the "combine" step, which happens after subproblems are solved. This requires either: A two-phase approach (divide all, then combine all) Storing partial results alongside pending subproblems Bottom-up iteration that builds from base cases upward

iterative_dc.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
# Iterative implementations of D&C algorithms
 
def merge_sort_iterative(arr):
    """
    Bottom-up iterative Merge Sort.
    
    Instead of dividing, we start from size-1 subarrays and 
    progressively merge into larger sorted subarrays.
    """
    n = len(arr)
    if n <= 1:
        return arr[:]
    
    # Start with individual elements (each is a sorted "subarray")
    result = arr[:]
    
    # Size of subarrays to merge: 1, 2, 4, 8, ...
    size = 1
    while size < n:
        # Merge pairs of subarrays of size 'size'
        for left in range(0, n, 2 * size):
            mid = min(left + size, n)
            right = min(left + 2 * size, n)
            result[left:right] = merge(result[left:mid], result[mid:right])
        
        size *= 2
    
    return result
 
 
def binary_search_iterative(arr, target):
    """
    Iterative Binary Search.
    
    Binary Search is easy to convert because there's no "combine" step.
    We just iterate, narrowing the range each time.
    """
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1
 
 
def quick_sort_iterative(arr):
    """
    Iterative Quick Sort using explicit stack.
    
    Stack stores ranges (left, right) to be sorted.
    Partitioning is done iteratively; recursion is simulated with stack.
    """
    result = arr[:]
    n = len(result)
    
    if n <= 1:
        return result
    
    # Stack stores (left, right) pairs representing ranges to sort
    stack = [(0, n - 1)]
    
    while stack:
        left, right = stack.pop()
        
        if left >= right:
            continue
        
        # Partition
        pivot_idx = partition(result, left, right)
        
        # Push subproblems onto stack
        # Push larger first so smaller is processed first (optimization)
        if pivot_idx - left > right - pivot_idx:
            stack.append((left, pivot_idx - 1))
            stack.append((pivot_idx + 1, right))
        else:
            stack.append((pivot_idx + 1, right))
            stack.append((left, pivot_idx - 1))
    
    return result
 
 
def partition(arr, left, right):
    """Lomuto partition scheme."""
    pivot = arr[right]
    i = left - 1
    
    for j in range(left, right):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i + 1], arr[right] = arr[right], arr[i + 1]
    return i + 1
 
 
def merge(left, right):
    """Merge two sorted arrays."""
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result
 
 
# Test iterative versions
import random
 
arr = [random.randint(0, 100) for _ in range(20)]
print(f"Original: {arr}")
print(f"Merge Sort (iterative): {merge_sort_iterative(arr)}")
print(f"Quick Sort (iterative): {quick_sort_iterative(arr)}")
 
arr_sorted = list(range(10))
print(f"
Binary Search for 7 in {arr_sorted}: index {binary_search_iterative(arr_sorted, 7)}")
print(f"Binary Search for 42 in {arr_sorted}: index {binary_search_iterative(arr_sorted, 42)}")

Recursive vs Iterative Trade-offs
Aspect	Recursive	Iterative
Clarity/Readability	Usually clearer	Can be complex
Stack space	O(depth) call stack	O(1) or explicit stack
Function call overhead	Per-call overhead	Avoided (loop only)
Debugging	Stack traces helpful	Manual state tracking
Tail call optimization	Language-dependent	Not applicable
Parallelization	Natural with fork-join	Requires more work

When to Use Iterative

Use iterative D&C when: (1) stack depth might be O(n) and you can't guarantee balanced division, (2) the language doesn't optimize tail calls and performance is critical, (3) you need fine-grained control over the execution order for parallelization, or (4) you're working with extremely large inputs where every byte of stack matters.

Common Recursive Patterns in D&C

Recognizing common recursive patterns helps you quickly design D&C solutions for new problems. Here are the major patterns: Pattern 1: Two-Way Divide (Most Common) def solve(input, lo, hi): if lo >= hi: # Base case return base_solution(input, lo) mid = lo + (hi - lo) // 2 left = solve(input, lo, mid) # Left half right = solve(input, mid + 1, hi) # Right half return combine(left, right) Examples: Merge Sort, Finding min/max, Counting inversions Pattern 2: Single Branch (Search/Optimization) def solve(input, lo, hi, target): if lo > hi: # Base case: not found return None mid = lo + (hi - lo) // 2 if check(input, mid, target): return mid # Base case: found elif go_left(input, mid, target): return solve(input, lo, mid - 1, target) else: return solve(input, mid + 1, hi, target) Examples: Binary Search, Finding rotation point

recursive_patterns.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
# Common D&C recursive patterns
 
# PATTERN 1: Two-Way Divide (split in half, process both)
def two_way_divide_template(arr, lo, hi):
    """
    Template for problems that split in half and combine results.
    Used for: Merge Sort, Count Inversions, Closest Pair, Max Subarray D&C
    """
    # Base case
    if lo >= hi:
        return handle_base(arr, lo, hi)
    
    mid = lo + (hi - lo) // 2
    
    # Recurse on both halves
    left_result = two_way_divide_template(arr, lo, mid)
    right_result = two_way_divide_template(arr, mid + 1, hi)
    
    # Combine results from both halves
    return combine_results(arr, lo, mid, hi, left_result, right_result)
 
 
# PATTERN 2: Single Branch (search, eliminate half)
def single_branch_template(arr, lo, hi, target):
    """
    Template for problems that eliminate half at each step.
    Used for: Binary Search, Finding peak, Search in rotated array
    """
    # Base case: empty range
    if lo > hi:
        return not_found()
    
    mid = lo + (hi - lo) // 2
    
    # Base case: found the answer
    if is_answer(arr, mid, target):
        return mid
    
    # Decide which half to search
    if should_go_left(arr, mid, target):
        return single_branch_template(arr, lo, mid - 1, target)
    else:
        return single_branch_template(arr, mid + 1, hi, target)
 
 
# PATTERN 3: Three-Way Combine (handle cross-boundary)
def three_way_combine_template(arr, lo, hi):
    """
    Template for problems where the answer might cross the midpoint.
    Used for: Maximum Subarray, Closest Pair near divide line
    """
    # Base case
    if lo == hi:
        return arr[lo]
    
    mid = lo + (hi - lo) // 2
    
    # Recurse on both halves
    left_result = three_way_combine_template(arr, lo, mid)
    right_result = three_way_combine_template(arr, mid + 1, hi)
    
    # Handle cross-boundary case
    cross_result = handle_crossing(arr, lo, mid, hi)
    
    # Answer is best of all three options
    return best_of(left_result, right_result, cross_result)
 
 
# PATTERN 4: Tree Recursion (process tree structure)
def tree_recursion_template(node):
    """
    Template for D&C on tree structures.
    Used for: Tree height, Tree diameter, LCA, Tree DP
    """
    # Base case: null node
    if node is None:
        return identity_value()
    
    # Base case: leaf node (optional optimization)
    if is_leaf(node):
        return leaf_value(node)
    
    # Recurse on children
    left_result = tree_recursion_template(node.left)
    right_result = tree_recursion_template(node.right)
    
    # Combine with current node
    return combine_with_node(node, left_result, right_result)
 
 
# PATTERN 5: Multi-Way Divide (more than 2 subproblems)
def multi_way_divide_template(arr, divisions=3):
    """
    Template for dividing into more than 2 subproblems.
    Used for: Strassen's variation, Some geometric algorithms
    """
    n = len(arr)
    
    # Base case
    if n <= threshold:
        return solve_directly(arr)
    
    # Divide into 'divisions' parts
    part_size = n // divisions
    parts = [arr[i*part_size:(i+1)*part_size] for i in range(divisions-1)]
    parts.append(arr[(divisions-1)*part_size:])  # Last part gets remainder
    
    # Recurse on all parts
    results = [multi_way_divide_template(part, divisions) for part in parts]
    
    # Combine all results
    return combine_multi(results)
 
 
# Placeholder functions for the templates
def handle_base(arr, lo, hi): return None
def combine_results(arr, lo, mid, hi, left, right): return None
def not_found(): return -1
def is_answer(arr, mid, target): return arr[mid] == target
def should_go_left(arr, mid, target): return arr[mid] > target
def handle_crossing(arr, lo, mid, hi): return 0
def best_of(*args): return max(args)
def identity_value(): return 0
def is_leaf(node): return node.left is None and node.right is None
def leaf_value(node): return node.val
def combine_with_node(node, left, right): return node.val + left + right
def solve_directly(arr): return sum(arr)
def combine_multi(results): return sum(results)
threshold = 10

Pattern Recognition Accelerates Design

When facing a new D&C problem, first identify which pattern applies. Is it a two-way split? A search that eliminates half? A tree structure? Once you identify the pattern, the template gives you the structure—you just need to fill in the problem-specific logic for divide, combine, and base cases.

4 / 4

solve(problem) = if problem is small enough: return direct_solution(problem) else: subproblems = divide(problem) subsolutions = [solve(subproblem) for subproblem in subproblems] return combine(subsolutions)

Recursion in Action: D&C Algorithms

Algorithm

Recursive Call Pattern

What Recursion Manages

Merge Sort

Two calls on each half

Sorting state for each subarray

Binary Search

One call on selected half

Search range boundaries

Quick Sort

Two calls on partitions

Partition boundaries, pivot positions

Tree Traversal

Calls on left and right subtrees

Current position in tree

Closest Pair

Two calls on point subsets

Subset boundaries, minimum distances

Strassen's

Seven calls on submatrices

Submatrix positions and intermediate products

Level 0: [n elements] Work: O(n) merge / Level 1: [n/2] [n/2] Work: 2 × O(n/2) = O(n) / \ / Level 2: [n/4][n/4][n/4][n/4] Work: 4 × O(n/4) = O(n) ... ... ... ... Level log(n): [1][1][1][1]...[1][1] Work: n × O(1) = O(n)

# Visualizing recursion trees def visualize_merge_sort_tree(n, level=0, label="root"): """ Prints the recursion tree for Merge Sort. Shows how the problem divides at each level. """ indent = " " * level work_at_node = n # Merge operation costs O(n) print(f"{indent}[{label}] size={n}, merge_cost={work_at_node}") if n <= 1: print(f"{indent} (base case)") return work_at_node mid = n // 2 # Recursive calls left_work = visualize_merge_sort_tree(mid, level + 1, "L") right_work = visualize_merge_sort_tree(n - mid, level + 1, "R") return work_at_node + left_work + right_work def visualize_binary_search_tree(n, level=0, target_side="both"): """ Visualize Binary Search recursion tree. Note: Only ONE branch is taken at each level (unlike Merge Sort). """ indent = " " * level work_at_node = 1 # O(1) comparison print(f"{indent}[search in size={n}] cost={work_at_node}") if n <= 1: print(f"{indent} (base: found or not in empty range)") return work_at_node # In Binary Search, we only go ONE direction (simulating 50% chance each way) mid = n // 2 if target_side == "left": return work_at_node + visualize_binary_search_tree(mid, level + 1, "left") else: return work_at_node + visualize_binary_search_tree(n - mid - 1, level + 1, "right") def analyze_recursion_tree(n, branching_factor, size_divisor, work_per_node): """ General analysis of a D&C recursion tree. Parameters: - n: problem size - branching_factor (a): number of subproblems at each node - size_divisor (b): each subproblem is size n/b - work_per_node: function that computes work at node given size Returns total work done. """ if n < 1: return 0 # Work at this node node_work = work_per_node(n) if n == 1: return node_work # Recursive: 'branching_factor' children, each with size n/size_divisor child_work = 0 subproblem_size = max(1, n // size_divisor) for _ in range(branching_factor): child_work += analyze_recursion_tree( subproblem_size, branching_factor, size_divisor, work_per_node ) return node_work + child_work # Examples print("=== Merge Sort Recursion Tree (n=8) ===") total = visualize_merge_sort_tree(8) print(f"Total work: {total}") print() print("=== Binary Search Recursion Tree (n=16) ===") total = visualize_binary_search_tree(16, target_side="right") print(f"Total work: {total}") print() print("=== General D&C Analysis ===") # Merge Sort: a=2, b=2, f(n)=n → Total O(n log n) print(f"Merge Sort (n=1000): {analyze_recursion_tree(1000, 2, 2, lambda n: n)}") # Binary Search: a=1, b=2, f(n)=1 → Total O(log n) print(f"Binary Search (n=1000): {analyze_recursion_tree(1000, 1, 2, lambda n: 1)}")

Pattern

Branching

Per-Level Work

Total Complexity

Linear (Binary Search)

O(1)

O(log n)

Balanced (Merge Sort)

2, halving

O(n) per level

O(n log n)

Heavy leaves (many small)

2, halving

O(1) per node

O(n)

Heavy root

2, halving

O(n²) per node

O(n²)

Strassen's

7, halving

O(n²)

O(n^2.81)

# Example: Proving Merge Sort correctness by induction def merge_sort(arr): """ Merge Sort with inline correctness annotations. CORRECTNESS CLAIM: merge_sort(arr) returns a sorted permutation of arr. """ # BASE CASE if len(arr) <= 1: # PROOF: An array of length 0 or 1 is trivially sorted. # It's also trivially a permutation of itself. return arr[:] mid = len(arr) // 2 # INDUCTIVE HYPOTHESIS (for recursive calls): # Assume merge_sort correctly returns sorted permutations for smaller arrays. left = merge_sort(arr[:mid]) # By IH: left is a sorted permutation of arr[:mid] right = merge_sort(arr[mid:]) # By IH: right is a sorted permutation of arr[mid:] # INDUCTIVE STEP: Prove merge produces correct result result = merge(left, right) # Claim: result is a sorted permutation of arr # Proof sketch: # 1. left contains exactly arr[:mid]'s elements (by IH, it's a permutation) # 2. right contains exactly arr[mid:]'s elements (by IH) # 3. merge combines ALL elements from left and right (see merge implementation) # 4. Therefore result contains exactly arr's elements: it's a permutation ✓ # 5. merge compares and selects smallest available elements in order # 6. Since left and right are each sorted, and we always take the smaller, # result is sorted ✓ return result def merge(left, right): """ Merge two sorted arrays into one sorted array. PRECONDITION: left and right are sorted. POSTCONDITION: returns sorted array containing all elements of left and right. """ result = [] i = j = 0 # LOOP INVARIANT: # - result contains the i smallest elements of left and j smallest of right # - result is sorted # - all elements in result are smaller than left[i] and right[j] while i < len(left) and j < len(right): if left[i] <= right[j]: # left[i] is smallest remaining element result.append(left[i]) i += 1 else: # right[j] is smallest remaining element result.append(right[j]) j += 1 # At most one of these runs (the other is exhausted) result.extend(left[i:]) result.extend(right[j:]) # POSTCONDITION: result contains all elements, sorted ✓ return result # The beauty of this proof structure: # We only need to verify: # 1. Base case returns correct result (trivial) # 2. merge is correct given sorted inputs (local reasoning) # # We DON'T need to trace through the entire recursion tree! # The induction handles all levels automatically.

Algorithm

Recursion Depth

Stack Space

Notes

Merge Sort

O(log n)

Balanced halving

Binary Search

O(log n)

Single recursive call

Quick Sort (balanced)

O(log n)

When pivots split evenly

Quick Sort (worst)

O(n)

When pivots always at edge

Clever Quick Sort

O(log n)

Tail recursion on larger half

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

import sys # Demonstrate stack depth in D&C algorithms def merge_sort_with_depth_tracking(arr, depth=0): """ Merge Sort that tracks maximum recursion depth. """ global max_depth max_depth = max(max_depth, depth) if len(arr) <= 1: return arr[:] mid = len(arr) // 2 left = merge_sort_with_depth_tracking(arr[:mid], depth + 1) right = merge_sort_with_depth_tracking(arr[mid:], depth + 1) return merge(left, right) def quick_sort_worst_case(arr, depth=0): """ Quick Sort with worst-case pivot selection (always first element). Demonstrates O(n) stack depth on sorted input. """ global max_depth max_depth = max(max_depth, depth) if len(arr) <= 1: return arr[:] pivot = arr[0] # Always pick first - bad for sorted input! left = [x for x in arr[1:] if x < pivot] right = [x for x in arr[1:] if x >= pivot] # Two recursive calls - both contribute to depth return quick_sort_worst_case(left, depth + 1) + [pivot] + quick_sort_worst_case(right, depth + 1) def quick_sort_tail_optimized(arr, depth=0): """ Quick Sort with tail call optimization: Always recurse on smaller partition first, then iterate on larger. This limits stack depth to O(log n). """ global max_depth while len(arr) > 1: max_depth = max(max_depth, depth) # Partition pivot = arr[len(arr) // 2] # Better pivot choice left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] # Recurse on SMALLER partition, iterate on larger if len(left) < len(right): sorted_left = quick_sort_tail_optimized(left, depth + 1) arr = right # Iterate on right (larger) result_prefix = sorted_left + middle else: sorted_right = quick_sort_tail_optimized(right, depth + 1) arr = left # Iterate on left (larger) result_suffix = middle + sorted_right # Handle base case if len(arr) <= 1: if 'result_prefix' in dir(): return result_prefix + arr + (result_suffix if 'result_suffix' in dir() else []) return arr return arr def merge(left, right): result = [] i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) result.extend(right[j:]) return result # Test stack depths import random for size in [100, 1000, 10000]: # Merge Sort - always O(log n) depth max_depth = 0 arr = [random.randint(0, 1000) for _ in range(size)] merge_sort_with_depth_tracking(arr) print(f"Merge Sort n={size}: max depth = {max_depth}, log₂(n) ≈ {size.bit_length()}") print() # Quick Sort worst case - O(n) depth on sorted input # Warning: May cause stack overflow for large n! for size in [100, 500, 1000]: max_depth = 0 arr = list(range(size)) # Already sorted - worst case for naive Quick Sort try: sys.setrecursionlimit(size + 100) quick_sort_worst_case(arr) print(f"Quick Sort (worst) n={size}: max depth = {max_depth}") except RecursionError: print(f"Quick Sort (worst) n={size}: STACK OVERFLOW!")

CALLER: solve(problem_n) │ ├─→ CHECK: Is this a base case? │ │ │ ├─ YES: Return direct solution, pop stack frame │ │ │ └─ NO: Continue to divide │ ├─→ DIVIDE: Split into subproblems │ ├─→ RECURSE #1: solve(subproblem_1) │ │ │ └─ (new stack frame, entire process repeats for subproblem_1) │ │ │ └─→ Returns subsolution_1 │ ├─→ RECURSE #2: solve(subproblem_2) │ │ │ └─ (new stack frame, entire process repeats for subproblem_2) │ │ │ └─→ Returns subsolution_2 │ ├─→ COMBINE: Merge subsolution_1 and subsolution_2 │ └─→ RETURN: combined solution to CALLER

# Detailed trace of a D&C call call_id = 0 def merge_sort_traced(arr, depth=0): """ Merge Sort with detailed tracing of call lifecycle. """ global call_id my_id = call_id call_id += 1 indent = " " * depth # ENTRY: New call begins print(f"{indent}[CALL {my_id}] ENTER: arr={arr}") # STEP 1: Base case check if len(arr) <= 1: print(f"{indent}[CALL {my_id}] BASE CASE: returning {arr}") return arr[:] # STEP 2: Divide mid = len(arr) // 2 left_arr = arr[:mid] right_arr = arr[mid:] print(f"{indent}[CALL {my_id}] DIVIDE: left={left_arr}, right={right_arr}") # STEP 3a: First recursive call (blocks until complete) print(f"{indent}[CALL {my_id}] RECURSE LEFT...") left_sorted = merge_sort_traced(left_arr, depth + 1) print(f"{indent}[CALL {my_id}] LEFT RETURNED: {left_sorted}") # STEP 3b: Second recursive call (blocks until complete) print(f"{indent}[CALL {my_id}] RECURSE RIGHT...") right_sorted = merge_sort_traced(right_arr, depth + 1) print(f"{indent}[CALL {my_id}] RIGHT RETURNED: {right_sorted}") # STEP 4: Combine print(f"{indent}[CALL {my_id}] COMBINE: merging {left_sorted} and {right_sorted}") result = merge(left_sorted, right_sorted) # STEP 5: Return print(f"{indent}[CALL {my_id}] EXIT: returning {result}") return result def merge(left, right): result = [] i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) result.extend(right[j:]) return result # Trace a small example print("=== MERGE SORT TRACED ===") call_id = 0 result = merge_sort_traced([3, 1, 4, 2]) print(f" FINAL RESULT: {result}") # Output shows the complete lifecycle: # - How calls nest within each other # - How base cases terminate branches # - How results bubble up through the combine steps # - The order of operations (preorder: divide before recursing, # postorder: combine after returning)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

# Iterative implementations of D&C algorithms def merge_sort_iterative(arr): """ Bottom-up iterative Merge Sort. Instead of dividing, we start from size-1 subarrays and progressively merge into larger sorted subarrays. """ n = len(arr) if n <= 1: return arr[:] # Start with individual elements (each is a sorted "subarray") result = arr[:] # Size of subarrays to merge: 1, 2, 4, 8, ... size = 1 while size < n: # Merge pairs of subarrays of size 'size' for left in range(0, n, 2 * size): mid = min(left + size, n) right = min(left + 2 * size, n) result[left:right] = merge(result[left:mid], result[mid:right]) size *= 2 return result def binary_search_iterative(arr, target): """ Iterative Binary Search. Binary Search is easy to convert because there's no "combine" step. We just iterate, narrowing the range each time. """ left, right = 0, len(arr) - 1 while left <= right: mid = left + (right - left) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1 def quick_sort_iterative(arr): """ Iterative Quick Sort using explicit stack. Stack stores ranges (left, right) to be sorted. Partitioning is done iteratively; recursion is simulated with stack. """ result = arr[:] n = len(result) if n <= 1: return result # Stack stores (left, right) pairs representing ranges to sort stack = [(0, n - 1)] while stack: left, right = stack.pop() if left >= right: continue # Partition pivot_idx = partition(result, left, right) # Push subproblems onto stack # Push larger first so smaller is processed first (optimization) if pivot_idx - left > right - pivot_idx: stack.append((left, pivot_idx - 1)) stack.append((pivot_idx + 1, right)) else: stack.append((pivot_idx + 1, right)) stack.append((left, pivot_idx - 1)) return result def partition(arr, left, right): """Lomuto partition scheme.""" pivot = arr[right] i = left - 1 for j in range(left, right): if arr[j] <= pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1], arr[right] = arr[right], arr[i + 1] return i + 1 def merge(left, right): """Merge two sorted arrays.""" result = [] i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) result.extend(right[j:]) return result # Test iterative versions import random arr = [random.randint(0, 100) for _ in range(20)] print(f"Original: {arr}") print(f"Merge Sort (iterative): {merge_sort_iterative(arr)}") print(f"Quick Sort (iterative): {quick_sort_iterative(arr)}") arr_sorted = list(range(10)) print(f" Binary Search for 7 in {arr_sorted}: index {binary_search_iterative(arr_sorted, 7)}") print(f"Binary Search for 42 in {arr_sorted}: index {binary_search_iterative(arr_sorted, 42)}")

Recursive vs Iterative Trade-offs

Aspect

Recursive

Iterative

Clarity/Readability

Usually clearer

Can be complex

Stack space

O(depth) call stack

O(1) or explicit stack

Function call overhead

Per-call overhead

Avoided (loop only)

Debugging

Stack traces helpful

Manual state tracking

Tail call optimization

Language-dependent

Not applicable

Parallelization

Natural with fork-join

Requires more work

def solve(input, lo, hi): if lo >= hi: # Base case return base_solution(input, lo) mid = lo + (hi - lo) // 2 left = solve(input, lo, mid) # Left half right = solve(input, mid + 1, hi) # Right half return combine(left, right)

def solve(input, lo, hi, target): if lo > hi: # Base case: not found return None mid = lo + (hi - lo) // 2 if check(input, mid, target): return mid # Base case: found elif go_left(input, mid, target): return solve(input, lo, mid - 1, target) else: return solve(input, mid + 1, hi, target)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

# Common D&C recursive patterns # PATTERN 1: Two-Way Divide (split in half, process both) def two_way_divide_template(arr, lo, hi): """ Template for problems that split in half and combine results. Used for: Merge Sort, Count Inversions, Closest Pair, Max Subarray D&C """ # Base case if lo >= hi: return handle_base(arr, lo, hi) mid = lo + (hi - lo) // 2 # Recurse on both halves left_result = two_way_divide_template(arr, lo, mid) right_result = two_way_divide_template(arr, mid + 1, hi) # Combine results from both halves return combine_results(arr, lo, mid, hi, left_result, right_result) # PATTERN 2: Single Branch (search, eliminate half) def single_branch_template(arr, lo, hi, target): """ Template for problems that eliminate half at each step. Used for: Binary Search, Finding peak, Search in rotated array """ # Base case: empty range if lo > hi: return not_found() mid = lo + (hi - lo) // 2 # Base case: found the answer if is_answer(arr, mid, target): return mid # Decide which half to search if should_go_left(arr, mid, target): return single_branch_template(arr, lo, mid - 1, target) else: return single_branch_template(arr, mid + 1, hi, target) # PATTERN 3: Three-Way Combine (handle cross-boundary) def three_way_combine_template(arr, lo, hi): """ Template for problems where the answer might cross the midpoint. Used for: Maximum Subarray, Closest Pair near divide line """ # Base case if lo == hi: return arr[lo] mid = lo + (hi - lo) // 2 # Recurse on both halves left_result = three_way_combine_template(arr, lo, mid) right_result = three_way_combine_template(arr, mid + 1, hi) # Handle cross-boundary case cross_result = handle_crossing(arr, lo, mid, hi) # Answer is best of all three options return best_of(left_result, right_result, cross_result) # PATTERN 4: Tree Recursion (process tree structure) def tree_recursion_template(node): """ Template for D&C on tree structures. Used for: Tree height, Tree diameter, LCA, Tree DP """ # Base case: null node if node is None: return identity_value() # Base case: leaf node (optional optimization) if is_leaf(node): return leaf_value(node) # Recurse on children left_result = tree_recursion_template(node.left) right_result = tree_recursion_template(node.right) # Combine with current node return combine_with_node(node, left_result, right_result) # PATTERN 5: Multi-Way Divide (more than 2 subproblems) def multi_way_divide_template(arr, divisions=3): """ Template for dividing into more than 2 subproblems. Used for: Strassen's variation, Some geometric algorithms """ n = len(arr) # Base case if n <= threshold: return solve_directly(arr) # Divide into 'divisions' parts part_size = n // divisions parts = [arr[i*part_size:(i+1)*part_size] for i in range(divisions-1)] parts.append(arr[(divisions-1)*part_size:]) # Last part gets remainder # Recurse on all parts results = [multi_way_divide_template(part, divisions) for part in parts] # Combine all results return combine_multi(results) # Placeholder functions for the templates def handle_base(arr, lo, hi): return None def combine_results(arr, lo, mid, hi, left, right): return None def not_found(): return -1 def is_answer(arr, mid, target): return arr[mid] == target def should_go_left(arr, mid, target): return arr[mid] > target def handle_crossing(arr, lo, mid, hi): return 0 def best_of(*args): return max(args) def identity_value(): return 0 def is_leaf(node): return node.left is None and node.right is None def leaf_value(node): return node.val def combine_with_node(node, left, right): return node.val + left + right def solve_directly(arr): return sum(arr) def combine_multi(results): return sum(results) threshold = 10

Recursive Structure

The Recursive Heart of D&C

Why Recursion is Natural for D&C

The Recursion Tree Model

Reasoning about Recursive Correctness

Stack Space and Memory Considerations

Anatomy of a D&C Recursive Call

Iterative Alternatives to Recursion

Common Recursive Patterns in D&C

There’s more to understand.

Recursive Structure

The Recursive Heart of D&C

Why Recursion is Natural for D&C

The Recursion Tree Model

Reasoning about Recursive Correctness

Stack Space and Memory Considerations

Anatomy of a D&C Recursive Call

Iterative Alternatives to Recursion

Common Recursive Patterns in D&C

There’s more to understand.