Unit 4.17: Recursive Searching and Sorting

Recursive Traversal

Recursion can be used as an alternative to iteration for traversing data structures like String objects, arrays, and ArrayLists.

Task: Recursively printing characters of a string.

// In the main method ...
public static void printChars(String str) {
    if (str == null || str.isEmpty()) {
        return;
    } else {
        System.out.println(str.charAt(0));
        printChars(str.substring(1));
    }
}

Task: Recursively printing a string in reverse.

// In the main method ...
public static void printReverse(String str) {
    if (str.length() > 0) {
        printReverse(str.substring(1)); // Recursive call first
        System.out.print(str.substring(0, 1)); // Print after call (results in reverse)
    }
}

Binary Search

Binary search is a highly efficient algorithm for finding an element in a sorted collection. It works by repeatedly dividing the search interval in half.

Binary Search Implementation

The binary search algorithm can be implemented either iteratively or recursively. Below is a recursive implementation.

Task: Performing a recursive binary search on a sorted array.

// In the main method ...
public static int binarySearch(int[] arr, int target, int low, int high) {
    // Base case: interval is empty, target not found
    if (low > high) {
        return -1;
    }
    
    int mid = (low + high) / 2;
    
    if (arr[mid] == target) {
        return mid; // Target found
    } else if (arr[mid] < target) {
        // Recursive step: Search upper half (right side)
        return binarySearch(arr, target, mid + 1, high);
    } else {
        // Recursive step: Search lower half (left side)
        return binarySearch(arr, target, low, mid - 1);
    }
}

Merge Sort

Merge sort is an efficient, recursive sorting algorithm that follows the "divide and conquer" strategy.

Merge Sort Implementation

The merge step creates a temporary array to hold the merged elements before copying them back.

Task: Implementing the full Merge Sort algorithm.

// In the main method ...
// Main sort function
public static void sort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        
        // Recursively sort first and second halves
        sort(arr, left, mid);
        sort(arr, mid + 1, right);
        
        // Merge the sorted halves
        merge(arr, left, mid, right);
    }
}

// Merges two subarrays of arr[]
public static void merge(int[] arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    int[] L = new int[n1];
    int[] R = new int[n2];
    
    for (int i = 0; i < n1; ++i) L[i] = arr[left + i];
    for (int j = 0; j < n2; ++j) R[j] = arr[mid + 1 + j];
        
    int i = 0, j = 0, k = left;
    
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    
    while (i < n1) { arr[k] = L[i]; i++; k++; }
    while (j < n2) { arr[k] = R[j]; j++; k++; }
}

Exclusion Statement: The implementation of merge sort is complex and typically requires a temporary array. For the AP exam, you are only responsible for understanding the recursive structure and tracing the steps of the process.

Heap Sort (Supplemental)

Heap sort is a comparison-based sorting algorithm that uses a Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place it at the end, but it uses a heap to find the maximum much faster.

Heap Sort Implementation

The heapify step is inherently recursive as it propagates the "sinking" of an element down the tree.

Task: Implementing the Heap Sort algorithm.

// In the main method ...
public static void heapSort(int[] arr) {
    int n = arr.length;

    // Build heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // One by one extract an element from heap
    for (int i = n - 1; i > 0; i--) {
        // Move current root to end
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // call max heapify on the reduced heap
        heapify(arr, i, 0);
    }
}

// To heapify a subtree rooted with node i which is an index in arr[]
public static void heapify(int[] arr, int n, int i) {
    int largest = i; // Initialize largest as root
    int l = 2 * i + 1; // left = 2*i + 1
    int r = 2 * i + 2; // right = 2*i + 2

    // If left child is larger than root
    if (l < n && arr[l] > arr[largest])
        largest = l;

    // If right child is larger than largest so far
    if (r < n && arr[r] > arr[largest])
        largest = r;

    // If largest is not root
    if (largest != i) {
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;

        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}

Exclusion Statement: Heap sort and the Binary Heap data structure are not part of the AP Computer Science A course or exam. This section is provided for advanced study and comparison of $O(n \log n)$ algorithms.