Unit 10 Recursion

• Intro to Recursion
• Merge Sort
  • Recursion Trees

Intro to Recursion

• 5-7.5% of the AP Exam, mainly in the multiple choice section
• A recursive method is method that calls itself.
• It contains at least one base case that halts recursion and once recursive call
• Each recursive call has own local variables
• Parameter values take progress of recursive process
• A recursion can be replaced with an iterative and give the same result
• Recursion can traverse String, array, and ArrayList objects

public static void simplerRecur(int n) {
    System.out.println(n);
    
    if (n > 2)
        simplerRecur(n-1); 
    System.out.println(n);
}
simplerRecur(4);

4
3
2
2
3
4

public static int simpleRecur2(int n) {
    if (n == 0)
        return 0;
    return n + simpleRecur2(n/2);
}
simpleRecur2(8);

15

public static void mystery (String s) {
    if (s.length() > 1) {
        mystery(s.substring(2));
        System.out.print(s.substring(0,1));
    }
}
mystery("computer");

eumc

Merge Sort

• Merge Sort can be used to sort ArrayLists

• Uses a Divide and Conquer algorithm to Sort ArrayList

  • Divides the array into halves, and then calls itself for the two different halves in order to sort them
  • merges the two sorted halves into one lists

• Merging Values into One Sorted Array

  • copy the original elements into a temporary array
  • work from left to right in each virtual array to compare element and return them to the correct order in the original array

Way to Think About It: mergeSort (myList) { mergeSort(left); mergeSort(right); mergeSort (left & right) }

First, the mergeSort function splits the ArrayList into half, and then takes the left side of the list. It then calls mergeSort again and then halves the list, and does this two more times. Eventually, it is left with just 5 after sorting using all of mergeSort(left).

Then, it goes back to the third step with just the 5 and 25, and looks at the right side of that one section. It compares the two halves, 5 and 25, and then sorts it, keeping the 5 before the 25 and recurses its way back to the ArrayList in the beginning.

We then go back down one more half where we have the 5, 25, 8, and -9. Because we had already sorted the left side of that list, we then go to the right side with the 8 and -9. We then sort the left side where we get 8 and then the right side with -9.

After this, the mergeSort() sorts -9 and 8 into the right order, and then recurses it once again 8 and -9 with the sorted -9 and 8 instead.

Because the four of the numbers for the left side of the original list were not in the correct order overall, mergeSort is once again called and the list is sorted with the correct order for just the left side, now containing -9, 5, 8, 25.

This process is then repeated, but for the right half of the ArrayList. It keeps slitting the list in half, sorting it, and then bringing it to the level below, where eventually, the ArrayList is sorted and merged together, as shown in the image below.

This is a code segment that CollegeBoard had provided in order to see the recursion behind mergeSort(). The code calls mergeSort() on itself in order to sort the list and merge the halves until you reach the right order and final list.

Recursion Trees

Recursion trees are a method for visualizing each recursive case (everytime the method is called) until the base case is reached.

Recursive blocks call themselves. In order for them to finish, there must be some special case in which they don't call themselves. That is the base case, a simpler version of the block's script that doesn't call the block itself.

There is usually a conditional with two cases: a base case for the lowest level that stops the recursion from going on forever and a recursive case that calls the block itself at lower levels until it reaches the base case.

Note: If a block keeps recursively calling itself forever, the program is stuck in an infinite loop meaning that there isn't a base case or it is not accessible.