Using recursion, we can make our searching and sorting algorithms from Unit 7 much more concise, and we will also have new searching and sorting algorithms that may be more efficient than our previous algorithms!

Searching - Linear/Sequential Search

We already covered this iteratively in Topic 7.5. As a reminder, here is the iterative code:

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;
}

Here is the recursive version:

public static int recursiveLinearSearch(ArrayList<Integer> array, int n, int startingIndex) {
  if (array.get(startingIndex) == n) {
    return startingIndex; // base case #1: element found
  } else if (startingIndex == array.size() - 1) {
    return -1; //base case #2: element not found
  } else {
    //

Searching - Binary Search

Binary search is the new search algorithm that we'll learn in this unit, and it is quicker than linear sort. However, the tradeoff for the speed is that the list has to be presorted. Binary search will not work if the data is not presorted.

Here is its implementation, along with how it works both iteratively and recursively:

/** Uses binary search on a sorted ArrayList
*   1. Looks at the middle of the list, which divides it into two sublists
*   2. The left sublist is less than the middle and the right is greater
*   3. Compare the value to be searched for to the middle value
*   4. If this value > middle, repeat 1-3 to the right sublist
*   5. If this value < middle, repeat 1-3 to the left sublist
*   6. If this value = middle, return the middle value
*   7. Return -1 if value not found
*/
public static int binarySearch(ArrayList<Integer> array, int n) {
  int left = 0;
  int right = array.size() - 1;
  while (left <= right) { // left > right is "illegal"
    int middle = (left + right) / 2; // get the middle index of sublist
    if (n == array.get(middle)) { // item in middle of sublist
      return middle;
    } else if (n < array.get(middle)) { // item in left sublist
      right = middle - 1;
    } else if (n > array.get(middle)) { // item in right sublist, could just use else
      left = middle + 1;
    }
  }
  return -1; // item not in list
}

public static int recursiveBinarySearch(ArrayList<Integer> array, int n, int left, int right) {
  int middle = (left + right) / 2; // get the middle index of sublist
  if (left > right) { // base case #1: item not in list
    return -1;
  } else if (n == array.get(middle)) { // base case #2: item in middle of sublist
    return middle;
  } else if (n < array.get(middle)) { // 

Here is a visualization of binary search:

Courtesy of Study.com.

Sorting - Insertion Sort

We already covered this iteratively in Topic 7.6. As a reminder, here is the iterative code:

/** Uses insertion sort on an ArrayList
*   1. Assume the first element is already sorted
*   2. Select the second element
*   3. Insert it before the first element or keep it in place to make the first 2 elements sorted
*   4. Select the third element and insert it so that the first 3 elements are sorted
*   5. Repeat until all elements are sorted.
*/
public static ArrayList<Integer> insertionSort(ArrayList<Integer> array) {
  for (int i = 1; i < array.length(); i++) {
    int currentElement = array.get(i);
    int currentIndex = i;
    for (int j = i; j > 0 ; j--) {
      if (currentElement < array.get(j - 1)) {
        // shifting the item left until properly placed by swapping consecutive items
        int itemToRight = array.get(j - 1);
        array.set(j - 1, currentElement);
        array.set(j, itemToRight);
      }
    }
  }
  return array;
}

Here is the recursive version:

public static ArrayList<Integer> recursiveInsertionSort(ArrayList<Integer> array, int index) {
  if (index == array.size()) { // base case: end of list reached, list sorted
    return array;
  } else {
    int currentItem = array.get(index)
    for (int i = index; i > 0; i--) { // shifting item to the left until sorted
      if (currentItem < array.get(i - 1)) {
        int itemToRight = array.get(i - 1);
        array.set(i - 1, currentItem);
        array.set(i, itemToRight);
      }
    }
    return recursiveInsertionSort(array, index + 1); // 

Sorting: Selection Sort

We already covered this iteratively in Topic 7.6. As a reminder, here is the iterative code:

/** Uses 

Here is the recursive version:

public static ArrayList<Integer> recursiveSelectionSort(ArrayList<Integer> array, int index) {
  if (index == array.size()) {
    return array;
  } else {
    int smallestIndex = index;
    int smallestElement = array.get(index);
    for (int i = index + 1; i < array.size(); i++) {
      if (array.get(i) < smallestElement) {
        smallestIndex = i;
        smallestElement = array.get(i);
      }
    }
    if (smallestIndex > index) {
      int originalItem = array.get(index);
      array.set(index, smallestElement);
      array.set(smallestIndex, originalItem);
    }
    return recursiveSelectionSort(array, index + 1);
  }
}
//To use this method:
recursiveInsertionSort(array, 0);

Sorting: Merge Sort

Merge sort is the new sorting algorithm learned in this unit, and it is quicker than insertion and selection sort. However, the tradeoff for the speed is that the algorithm requires more memory.

Here is its implementation, along with how it works both iteratively and recursively:

/** Performs 

Here is a visual look at merge sort:

Courtesy of Techie Delight.

Closing — What's Next?

If you've made it this far, congratulations, you've reached the end of AP Computer Science A! By now, you should be an expert on control structures — loops, recursion, and conditional statements, object orientated programming — abstraction/method writing, encapsulation/class writing, inheritance, and polymormism, and basic data structures — 1-D and 2-D arrays and ArrayLists!

If you're interested in further pursuing computer science, what comes next?

Courtesy of GIPHY.

You will most likely take a set of two courses, one being a more mathematically orientated and the other being more programming orientated. The first is a discrete math class, which covers the theory of discrete sets, which consists of things that we can count on our fingers, like whole numbers, as opposed to continuous sets, which are uncountable, such as real numbers. In this class, you'll learn a lot of logic and proofs so that we can understand programs and algorithms more. You will also learn probability and state machines as well, which represent random algorithms and will help with machine learning and other fields where our methods are mostly consisting of random numbers with random outputs. Finally, you'll learn about graphs, which are a type of data structure that consists of different elements and connections between these elements.

On the other hand, the second Java course is a continuation of this course. You'll learn some advanced topics in inheritance and polymorphism with the introduction of the interface and the abstract class and also make better loops, recursion, and classes with what are known as invariants (which are the basis of the "Four Loopy Questions" in Unit 4). Then, you'll move onto more advanced data structures, including the following:

• The Linked List
• These do not have indices but just pointers between one element and the next (and sometimes previous)
• Hash maps and other maps
• These map one element to another which is like a dictionary word and its definition (the hash map uses a hash function like those described in Topic 9.7)
• Sets
• These are like lists, but are unordered and have nonduplicating items
• Trees
• These represent data in a branched structure, and are best when items have multiple different "levels"
• Graphs
• Explained above, these represent data and connections between this data

You'll learn about these data structures and also implement algorithms, being able to analyze how fast they run and how much memory they take up. Finally, you'll also learn to make GUIs, which are graphics which display information in a visual manner.

With AP CSA and these two courses, these set up the foundation for any computer science that you will do afterwards, like artificial intelligence and machine learning, algorithm analysis, programming language construction, graphics, web development, and so much more! The possibilities are endless! Moreover, there are many resources to learn these online as well and you don't need to go to a university to be a good programmer, but instead you can teach yourself and achieve great things!

If you have reached the end of this guide, thank you for sticking along on this journey through AP CSA. We as the Fiveable team have spent countless hours making and curating the best resources available for your use so that you can pass the AP exam and hopefully learn something new, fun, and insightful throughout this course that you can use later. We hope that you have found this information valuable and we wish you the best of luck on your AP exams and beyond!