Unit 10 - Recursion

• 10.2 Binary Search With Equations
• Merge Sort
  • Recursion Trees

This is what a recursion looks like where the example method is called within itself.

public static void example(int n) {
    if (n > 0)
        example (n-1);
}

In this example, the simplerRecur method is called within itself. So, simplerRecur(4) will result in printing 4 and then one less than it until the parameter is false. It then cycles back up to the top of the call stack. This is why it returns the 2 3 4 at the end.

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

In this, simpleRecur2(8) wil return 8 + simpleRecur2(4) and simpleRecur2(4) will return 4 + simpleRecur2(2). This process will continue until n = 0 and all the values will be added together.

8 + 4 + 2 + 1 + 0

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

15

This one is similar to the last example where it will add the values together but this has multiple recursive methods inside it. So, dblRecur(5) will return 5 + dblRecur(2) + dblRecur(1) and then dblRecur(2) and dblRecur(1) will have their own run through the method until n is no longer greater than 0.

public int dblRecur(int n) {
    if (n > 0)
        return n + dblRecur(n/2) + dblRecur(n/3);
    return 0;
}
dblRecur(5);

9

Recursion can also be seen will String objects. In this, mystery("computer") will first go through the mystery(s.substring(2)) which will result in a call stack with "computer", "mputer", "uter", "er", and " ". THe print statement will then print the first letter of those Strings so e u m c.

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

eumc

10.2 Binary Search With Equations

We start by taking the entire array, starting with the first and the last numbers, and find the midpoint. Starting number is 0, and end is 40, and the midpoint is 20.

Since 24 is greater than 20, we take the upper bound of the list, ignoring everything less that 22.The first number now becomes 22.

We identify the midpoint again, which is 30. Since the new midpoint is higher than 24, we now take the lower bound. Here, the last number becomes 28.

In this new bound, we find the midpoint again, which happens to be 24. So, we have found our target.

Now, lets say that the target was 23, instead of 24. The program would have to keep going from the midpoint of 24. Since 23 is less than 24, it takes the lower bound. However, this makes first, last and midpoint numbers 22.

Again, since 22 is less than 23, the first number becomes 24, and the last number stays 22. This becomes a problem since the first number is greater than the last, which is our base case. This tells the program that the number 23 isn’t in the list, and that it should end.

public class recursion{
    public static int recursionBinarySearch(int[] array, int first, int last, int target){
        int midpoint;

        //if the first number is greater than the last, the target number is not in the list
        if (first > last){
            System.out.println(-1);
            return -1;
        }
        else{
            midpoint = (first+last)/2;

            //take the upper bound if number is greater than midpoint
            if (array[midpoint] < target){
                return recursionBinarySearch(array, midpoint+1, last, target);
            }

            // take the lower bound if the number is lesser than midpoint
            if (array[midpoint] > target){
                return recursionBinarySearch(array, first,midpoint-1, target);
            }
        System.out.println("index of target: " + midpoint);
        return midpoint;
        }
    }

    public static void main(String[] args){
        // test array in main
        int[] test_array = new int[]{ 0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40 };
        recursion.recursionBinarySearch(test_array, 0, test_array.length, 24);
    }
}

recursion.main(null);

index of target: 12

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.

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.

public class example{
    static int foo(int n) {

        if (n < 0){
            return 1;
        }
        else{
            return foo(n-2) + foo(n-1);
        }

    }

    public static void main(String args[]){
        System.out.println(foo(3));
    }
}

example.main(null);

8