Recursive Searching and Sorting

Recursive Searching and Sorting: AP Computer Science A Study Guide

Hello, future programming wizards! Ready to dive into the magical world of recursion? It’s the part of computer science where functions get super introspective and start calling themselves. Think of it as a function looking in a mirror and saying, “Hey, how would you solve this?” 🤔✨

Searching Algorithms Using Recursion

Remember the good ol' linear search we covered in Unit 7? It's like finding Waldo in a crowd by checking every single person. Now let's make it a bit more dramatic by using recursion.

Iterative Linear Search:

public static int linearSearch(ArrayList<Integer> array, int n) {
    for (int i = 0; i < array.size(); i++) {
        if (array.get(i) == n) {
            return i;
        }
    }
    return -1;
}

Recursive Linear Search:

public static int recursiveLinearSearch(ArrayList<Integer> array, int n, int startingIndex) {
    if (startingIndex >= array.size()) {
        return -1; // Element not found
    }
    if (array.get(startingIndex) == n) {
        return startingIndex;
    }
    return recursiveLinearSearch(array, n, startingIndex + 1); // Next element, please!
}

// Call this method like so:
recursiveLinearSearch(array, n, 0);

Binary search is like playing a guessing game where you ask if the number is higher or lower than your guess. It’s super fast because it divides the array in half every time. Most importantly, unlike your infinite Minecraft world, the array must be sorted!

Iterative Binary Search:

public static int binarySearch(ArrayList<Integer> array, int n) {
    int left = 0, right = array.size() - 1;
    while (left <= right) {
        int middle = (left + right) / 2;
        if (array.get(middle) == n) {
            return middle;
        } else if (n < array.get(middle)) {
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }
    return -1; // Element not found
}

Recursive Binary Search:

public static int recursiveBinarySearch(ArrayList<Integer> array, int n, int left, int right) {
    if (left > right) {
        return -1; // Element not found
    }
    int middle = (left + right) / 2;
    if (array.get(middle) == n) {
        return middle;
    } else if (n < array.get(middle)) {
        return recursiveBinarySearch(array, n, left, middle - 1);
    } else {
        return recursiveBinarySearch(array, n, middle + 1, right);
    }
}

// Use it like this:
recursiveBinarySearch(array, n, 0, array.size() - 1);

Sorting Algorithms Using Recursion

Insertion sort is like sorting a hand of playing cards. You take one card at a time and place it in the correct position among the previously sorted cards.

Iterative Insertion Sort:

public static ArrayList<Integer> insertionSort(ArrayList<Integer> array) {
    for (int i = 1; i < array.size(); i++) {
        int current = array.get(i);
        int j = i - 1;
        while (j >= 0 && array.get(j) > current) {
            array.set(j + 1, array.get(j));
            j--;
        }
        array.set(j + 1, current);
    }
    return array;
}

Recursive Insertion Sort:

public static ArrayList<Integer> recursiveInsertionSort(ArrayList<Integer> array, int index) {
    if (index == array.size()) {
        return array; // Base case: Array is sorted
    }
    int current = array.get(index);
    int j = index - 1;
    while (j >= 0 && array.get(j) > current) {
        array.set(j + 1, array.get(j));
        j--;
    }
    array.set(j + 1, current);
    return recursiveInsertionSort(array, index + 1); // Next card please!
}

// Call this method like so:
recursiveInsertionSort(array, 0);

Selection sort involves repeatedly choosing the smallest (or largest) remaining element and moving it to its correct position.

Iterative Selection Sort:

public static ArrayList<Integer> selectionSort(ArrayList<Integer> array) {
    for (int i = 0; i < array.size() - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < array.size(); j++) {
            if (array.get(j) < array.get(minIndex)) {
                minIndex = j;
            }
        }
        int temp = array.get(minIndex);
        array.set(minIndex, array.get(i));
        array.set(i, temp);
    }
    return array;
}

Recursive Selection Sort:

public static ArrayList<Integer> recursiveSelectionSort(ArrayList<Integer> array, int index) {
    if (index == array.size()) {
        return array; // Base case: array sorted
    }
    int minIndex = index;
    for (int j = index + 1; j < array.size(); j++) {
        if (array.get(j) < array.get(minIndex)) {
            minIndex = j;
        }
    }
    if (minIndex != index) {
        int temp = array.get(minIndex);
        array.set(minIndex, array.get(index));
        array.set(index, temp);
    }
    return recursiveSelectionSort(array, index + 1); // Sorting next element
}

// Use it like this:
recursiveSelectionSort(array, 0);

Merge sort is like that episode of your favorite anime where the hero splits into multiple sub-heroes, sorts out their own arcs, and then reunites to win the battle efficiently.

Iterative Merge Sort: Iterative merge sort normally requires extra functions and structure, and it's generally less common to use iteratively compared to recursively.

Recursive Merge Sort:

public static void recursiveMergeSort(ArrayList<Integer> array, int left, int right) {
    if (left < right) {
        int middle = (left + right) / 2;
        recursiveMergeSort(array, left, middle);
        recursiveMergeSort(array, middle + 1, right);
        merge(array, left, middle, right);
    }
}

public static void merge(ArrayList<Integer> array, int left, int middle, int right) {
    int leftSize = middle - left + 1;
    int rightSize = right - middle;

    ArrayList<Integer> leftTemp = new ArrayList<>(leftSize);
    ArrayList<Integer> rightTemp = new ArrayList<>(rightSize);

    for (int i = 0; i < leftSize; i++) {
        leftTemp.add(array.get(left + i));
    }
    for (int i = 0; i < rightSize; i++) {
        rightTemp.add(array.get(middle + 1 + i));
    }

    int i = 0, j = 0, k = left;
    while (i < leftSize && j < rightSize) {
        if (leftTemp.get(i) <= rightTemp.get(j)) {
            array.set(k, leftTemp.get(i));
            i++;
        } else {
            array.set(k, rightTemp.get(j));
            j++;
        }
        k++;
    }
    while (i < leftSize) {
        array.set(k, leftTemp.get(i));
        i++;
        k++;
    }
    while (j < rightSize) {
        array.set(k, rightTemp.get(j));
        j++;
        k++;
    }
}

// Use it like this:
recursiveMergeSort(array, 0, array.size() - 1);

Well, buddy, you’ve cracked the code on recursion! 🎉 Just like mastering a double scoop ice cream stack, remember the key: start with the basics and build up.

Here’s what's next on your coding journey: Prepare to explore advanced courses like Discrete Math (logic, proofs, probability) and more Java shenanigans with advanced inheritance and data structures like Linked Lists, Hash Maps, and Trees. These are like leveling up from using a wooden sword to wielding Excalibur. 🗡️⚓

So whether you aim to build AI, analyze algorithms, or even develop the next viral app, you've got the foundational skills. Now, go forth and conquer the tech world—or at least your next AP exam. May your code be bug-free and your recursion base cases ever in reach! 🌟