Recursive Searching and Sorting

⚠ Optional chapter. Closes out the curriculum by combining Lessons 28.1-28.3: the same searching/sorting ideas, rewritten recursively.

Recursive Binary Search

The iterative binary search from Lesson 28.1 tracks left/right bounds in loop variables. A recursive version instead passes the shrinking range as parameters, with the range itself doing the job a while loop's condition did before:

public static int recursiveBinarySearch(int[] elements, int start, int end, int target)
{
    if (end < start)                          // base case 1: range is empty — not found
    {
        return -1;
    }
    int middle = (start + end) / 2;
    if (target == elements[middle])            // base case 2: found it
    {
        return middle;
    }
    else if (target < elements[middle])
    {
        return recursiveBinarySearch(elements, start, middle - 1, target); // search the left half
    }
    else
    {
        return recursiveBinarySearch(elements, middle + 1, end, target);   // search the right half
    }
}

This has two base cases (Ch.25.4's enum state machines had a preview of "more than one stopping condition" — the same idea applies here): a match at the middle, or an exhausted range. Removing the end < start check would mean a not-found search keeps recursing into an already-empty range forever — exactly the missing-base-case bug from Lesson 28.3.

Merge Sort: A Third Sorting Algorithm

Selection sort and insertion sort (Lesson 28.2) both cost roughly n² in the worst case. Merge sort is a divide-and-conquer algorithm — like binary search, it splits the problem in half repeatedly, which makes it substantially faster on large data (roughly n log n instead of n²):

1. Split the array into two halves.
2. Recursively sort each half (a single-element array is trivially already sorted — the base case).
3. Merge the two now-sorted halves back together, in order.

public static void mergeSort(int[] elements)
{
    int n = elements.length;
    int[] temp = new int[n]; // scratch space used during merging
    mergeSortHelper(elements, 0, n - 1, temp);
}

private static void mergeSortHelper(int[] elements, int from, int to, int[] temp)
{
    if (from >= to) return; // base case: a range of 0 or 1 elements is already sorted
    int middle = (from + to) / 2;
    mergeSortHelper(elements, from, middle, temp);      // recursively sort the left half
    mergeSortHelper(elements, middle + 1, to, temp);    // recursively sort the right half
    merge(elements, from, middle, to, temp);            // combine the two sorted halves
}

Tracing the split-then-merge structure for {86, 3, 43, 5}, using nested braces:

Split:  { {86, 3} , {43, 5} }
Split:  { { {86}, {3} } , { {43}, {5} } }   <- single elements: base case reached
Merge:  { {3, 86} , {5, 43} }
Merge:  { 3, 5, 43, 86 }

Like selection sort, merge sort's structure doesn't depend on the input's initial order — it always splits and merges the same way. But because its divide-and-conquer approach scales so much better than n² sorting, it's the fastest of the three algorithms in this curriculum, most of the time, especially as the data set grows.

Iterative vs. Recursive: Same Algorithm, Different Shape

Binary search exists in both forms (Lesson 28.1's iterative version, this lesson's recursive one) — a good concrete reminder of Lesson 28.3's point that many algorithms can be written either way. Iteration is usually preferred in real code (no risk of StackOverflowError, generally a bit more efficient) — but a recursive version can be more compact and can make a divide-and-conquer structure (like merge sort's) much more natural to express than an iterative equivalent would be.

Common Pitfalls

• Forgetting either base case in recursive binary search. Both the "found it" and "range exhausted" cases are needed — missing the exhausted-range check risks infinite recursion on a not-found search.
• Merging without first ensuring both halves are actually sorted. Merge sort's merge step assumes its two inputs are already individually sorted — that's exactly what the recursive calls before it guarantee.
• Assuming recursive is always "better" than iterative, or vice versa. Each has real tradeoffs (stack depth risk vs. code clarity) — the right choice depends on the specific algorithm and data size.

Key Takeaways

• Recursive binary search replaces loop-tracked bounds with a shrinking range passed as parameters, and needs two base cases: a match, or an exhausted range.
• Merge sort is a recursive, divide-and-conquer sort: split in half, recursively sort each half (base case: 1 element), then merge the sorted halves back together.
• Merge sort scales better than selection/insertion sort on large data (n log n vs. n²), and its performance doesn't depend on the input's initial order.
• The same algorithm can often be written iteratively or recursively — the choice is a real tradeoff, not a universal "better" answer either way.

Derived from csawesome-2026: unit-4-data-collections/4.17-recursive-searching-and-sorting.md (CSA 4.17)