10.1 Recursion

A method calling itself to repeat a certain number of times.

Popcorn Hack: What is recursion?

Vocabulary

Base Case - this sets the __ __ for when the recursion will stop
Formal Parameters - __ within the method (local variables)

Method Calling Itself

We will first be looking at how a method can call itself.

/* 
DO NOT RUN THIS
if you do run this accidentally press `ctrl + c` twice
*/

public class Recursion1 {
  public static void recursionCount(int n) { // original method definition
    System.out.println(n);
    //recursionCount(n - 1); // calling the method again
    // making it run-safe
  }

  public static void main(String[] args) {
    recursionCount(3); // original call of the method
  }
}

Recursion1.main(null);

In this example, you will receive an overflow error because the method is calling itself infinitely. To avoid this you would create a base case.

A base case usually uses an if-then statement to turn the loop off after a certain condition is met.

public class Recursion2 {
  public static void recursionCount(int n) {
    if (n <= 0) { // added base case, telling the program to stop when n is less than or equal to 0
      System.out.println("done");
    } else {
      System.out.println(n);
      recursionCount(n - 1); // method recursion
    }
  }

  public static void main(String[] args) {
    recursionCount(3); // calling original function
  }
}

Recursion2.main(null);

3
2
1
done

Popcorn Hack: Create your own quick recursive program.

public class RecursionTest {
    public static void recurse(int n) {
      if (n <= 0) { // added base case, telling the program to stop when n is less than or equal to 0
        System.out.println("done");
        return;
      } else {
        System.out.println(n);
        recurse(n-1); // method recursion
      }
    }
  
    public static void main(String[] args) {
      recurse(7); // calling original function
    }
  }
  RecursionTest.main(null);

7
6
5
4
3
2
1
done

Calling With Different Parameters

You can also call the method with multiple different parameters, also known as local variables.

In this example we call an integer and string.

public class Recursion3 {
  public static void recursionPrint(int n, String a) { // formal parameters are within this method
    if (n <= 0) { // base case
      System.out.println("done");
      return;
    }

    System.out.println("n = " + n + " a = " + a); // printing each var with each call of the method

    String addChar = a + "!"; // mutating string with each recursion
    int addN = n - 1; // mutating integer with each recursion

    recursionPrint(addN, addChar); // recursive function
  }

  public static void main(String[] args) {
    recursionPrint(5, "test"); // initial call
  }
}
Recursion3.main(null);

n = 5 a = test
n = 4 a = test!
n = 3 a = test!!
n = 2 a = test!!!
n = 1 a = test!!!!
done

Here we just convert each string and subtract one from every previous number.

Capturing Progression Through Recursion

You can also capture the progression through recursion. This is useful for doing specific tasks in specific steps through recursion.

public class Recursion4 {
  public static void recursionCount(int n, int progress) {
    if (n <= 0) {
      System.out.println("done");
    } else {
      if (n == progress) {
        System.out.println("Reached halfway through the array."); // special action done only when the program has reached a certain point
      }
      System.out.println(n);
      recursionCount(n - 1, progress); // recursive call
    }
  }

  public static void main(String[] args) {
    int n = 6;
    int progress = n / 2; // progress is set to half of the array length
    recursionCount(n, progress); // initial call
  }
}

Recursion4.main(null);

6
5
4
Reached halfway through the array.
3
2
1
done

Popcorn Hack: What other situations could we use capturing progression for?

Converting Recursion to Iteration

Any recursive process can be made iterative, however this is not needed for the AP test. It is, however, still useful.

Recursive Version

public class Recursion5 {
  public static void recursionCount(int n) {
    if (n <= 0){
      System.out.println("done");
    } else {
      System.out.println(n);
      recursionCount(n - 1); // recursive function
    }
  }

  public static void main(String[] args) {
    recursionCount(3); // initial call
  }
}

Recursion5.main(null);

3
2
1
done

Iterative Version

public class Iteration {
  public static void iterationCount(int n) {
    for (int i = n; i >= 1; i--) { // using a for loop to iterate, notice we go only so i is greater than 1 and not 0
      System.out.println(i);
    }
    System.out.println("done");
  }
  
  public static void main(String[] args) {
    iterationCount(3); // same initial call
  }
}

Iteration.main(null);

3
2
1
done

Popcorn Hacks: We we go only so i is greater than or equal to 1 and not 0. Why?

Also when you index, you’ll start from 0, so it’ll stop at 0 instead of one.

Traversing With Recursion

You can traverse many things with recursion. Here I will show traversal through a string, array, and an ArrayList object.

String Traversal

You can traverse through a string, finding a specific character in the string.

public class FindChar {
    public static boolean findChar(String s, char target, int index) {
        if (index >= s.length()) { // checks for if the index we are looking for is greater than the word length
            return false;
        }

        if (s.charAt(index) == target) { // checks for if there is a character the index we are searching
            return true;
        }

        return findChar(s, target, index + 1); // recalls method, recursion
    }

    public static void main(String[] args) {
        String sampleString = "words"; // example string
        char targetChar = 's'; // character we are looking for

        System.out.println("Sample String: " + sampleString);

        boolean isCharFound = findChar(sampleString, targetChar, 0); // checks if the character we are looking for is found, based on boolean

        if (isCharFound) {
            System.out.println("Character '" + targetChar + "' is found."); // if it is found, show this
        } else {
            System.out.println("Character '" + targetChar + "' is not found."); // if not show this
        }
    }
}

FindChar.main(null);

Sample String: words
Character 's' is found.

You can also find and print a certain range of characters from the string.

public class PrintRange {
    public static void printRange(String s, int startIndex, int endIndex) {
        if (startIndex < 0 || endIndex > s.length() || startIndex >= endIndex) { // checks for invalid declaration or end (negative index, index larger than string length, index start has reached the end)
            return;
        }

        System.out.print(s.charAt(startIndex)); // print the characters in the range
        printRange(s, startIndex + 1, endIndex); // recursive calling
    }

    public static void main(String[] args) {
        String sampleString = "example"; // string
        int startIndex = 0;
        int endIndex = 5;
        
        System.out.println("Word: " + sampleString);
        System.out.println("Start: " + startIndex + ", End: " + endIndex);

        System.out.print("Characters in the specified range: ");
        printRange(sampleString, startIndex, endIndex); // initial call
    }
}

PrintRange.main(null);

Word: example
Range 1: Start: 0, End: 5
Range 2: Start: 2, End: 6
Characters in Range 1: exampl
Characters in Range 2: ample

Popcorn Hack: Make it so that we can find two different ranges and print them.

public class PrintRange {
    public static void printRange(String s, int startIndex, int endIndex) {
        if (startIndex < 0 || endIndex > s.length() || startIndex >= endIndex) {
            return;
        }

        for (int i = startIndex; i <= endIndex; i++) {
            System.out.print(s.charAt(i));
        }
    }

    public static void main(String[] args) {
        String sampleString = "example";
        int startIndex1 = 0;
        int endIndex1 = 5;
        int startIndex2 = 2;
        int endIndex2 = 6;
        
        System.out.println("Word: " + sampleString);
        System.out.println("Range 1: Start: " + startIndex1 + ", End: " + endIndex1);
        System.out.println("Range 2: Start: " + startIndex2 + ", End: " + endIndex2);

        System.out.print("Characters in Range 1: ");
        printRange(sampleString, startIndex1, endIndex1);
        System.out.println();

        System.out.print("Characters in Range 2: ");
        printRange(sampleString, startIndex2, endIndex2);
        System.out.println();
    }
}

PrintRange.main(null)

Word: example
Range 1: Start: 0, End: 5
Range 2: Start: 2, End: 6
Characters in Range 1: exampl
Characters in Range 2: ample

Array Traversal

You can also traverse arrays using recursion.

public class ArrayTraversal {
  public static int findIndex(int[] arr, int targetIndex, int currentIndex) {
    if (currentIndex < 0 || currentIndex >= arr.length) { // checks for invalid (index less than 0, index greater than array length)
      return -1; // returns invalid
    }

    if (currentIndex == targetIndex) { // if the index is found
      return currentIndex;
    }

    return findIndex(arr, targetIndex, currentIndex + 1); // recursion
  }

  public static void main(String[] args) {
    int[] sampleArray = {1, 4, 6, 8, 4, 9, 12};
    int targetIndex = 2; // target

    int foundIndex = findIndex(sampleArray, targetIndex, 0);

    if (foundIndex != -1) { // checks what has been outputted
      int value = sampleArray[foundIndex]; // found index value
      System.out.println("Index " + targetIndex + " is found in the array at position " + foundIndex + " with a value of " + value); // found
    } else {
      System.out.println("Index " + targetIndex + " is not found in the array."); // not found
    }
  }
}

ArrayTraversal.main(null);

Index 2 is found in the array at position 2 with a value of 6

ArrayList Object Traversal

We can also traverse the ArrayList object.

import java.util.ArrayList;

public class ArrayListTraversal {
    public static int findIndex(ArrayList<Integer> list, int targetIndex, int currentIndex) {
        if (currentIndex < 0 || currentIndex >= list.size()) { // checks for invalid
            return -1;
        }

        if (currentIndex == targetIndex) { // finds index
            return currentIndex;
        }

        return findIndex(list, targetIndex, currentIndex + 1); // recusion
    }

    public static void main(String[] args) {
        ArrayList<Integer> sampleList = new ArrayList<>(); // created ArrayList object
        sampleList.add(1);
        sampleList.add(4);
        sampleList.add(6);
        sampleList.add(8);
        sampleList.add(4);
        sampleList.add(9);
        sampleList.add(12);

        int targetIndex = 2; // target

        int foundIndex = findIndex(sampleList, targetIndex, 0);

        if (foundIndex != -1) { // checks for if found or not
            int value = sampleList.get(foundIndex); // gets found index from ArrayList object
            System.out.println("Index " + targetIndex + " is found in the ArrayList at position " + foundIndex + " with a value of " + value);
        } else {
            System.out.println("Index " + targetIndex + " is not found in the ArrayList.");
        }
    }
}

ArrayListTraversal.main(null);

Index 2 is found in the ArrayList at position 2 with a value of 6

Conclusion

Must Knows:

How to create recursive code (recalling a method within itself, with parameters that change)
Record progression through recursion (completing certain tasks through the progression)
Traversal of strings, arrays, and the ArrayList object

Overall, recursion is useful as an alternative to iteration. Recursion is usually chosen for problems that can naturally be divided into parts, like sorting which will be talked about in the next part.

10.2 Binary Search

Binary Search vs Linear Search

target number - 24

intArray - 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40

Popcorn hack:

How many times iterated through for Linear Search?

Answer: 13

Example of Binary Search with Recursion

public class BinarySearch {
    public static void main(String[] args) {
        int[] intArray = {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40}; // Example array
        int target = 8; // Example target value
        int result = recBinarySearch(intArray, 0, intArray.length - 1, target);

        if (result == -1) {
            System.out.println("Target not found in the array.");
        } else {
            System.out.println("Target found at index: " + result);
        }
    }

    public static int recBinarySearch(int[] intArray, int lowPosition, int highPosition, int target) { //method
        if (lowPosition > highPosition) {
            return -1; // Element not found in the array
        } else {
            int midPosition = (lowPosition + highPosition) / 2;
            if (intArray[midPosition] < target) {
                return recBinarySearch(intArray, midPosition + 1, highPosition, target);
            } else if (intArray[midPosition] > target) {
                return recBinarySearch(intArray, lowPosition, midPosition - 1, target);
            } else {
                return midPosition; // Element found at midPosition
            }
        }
    }
}

BinarySearch.main(null);

Target found at index: 4

Call 1

Index = 0 - 20, midPosition = 10, midPosition value = 20

Since 24 > 20,

then…

lowPosition = midPosition + 1 = 11 highPosition = highPosition = 20

Call 2

Index = 11-20, midPosition index = 15, midPosition value = 30

Since 24 < 30,

then…

lowPosition = lowPosition = 11 high position = midPosition - 1 = 14

Call 3

Index = 11-14, midPosition index = 12, midPosition value = 24

Since 24 = 24,

then…

return midPosition;

In total, our recursive calls to the method 3 times.

Recursive Logic behind Merge Sort

What is Merge Sort? Merge sort is a recursive sorting algorithm that can be used to sort elements in an array or ArrayList

Follows a divide and conquer approach

Link

Notes:

List: [38,27,43,3,9,82,10] 

sudocode version:
mergeSort(List) {
    mergeSort(left)
    mergeSort(right)
    merge(left & right)

} 

Must finish call above it in order to finish the call

Call 1:

Splitting List into half
Left side: [38, 27, 43, 3]
Must finish call 1 in order to do the right side and do the merge
Recursively calls mergesort and splits the list in half again

Call 2:

New Left side List: [38, 27]
Method calls are stacking on top of each other

Notes:

Element 5 can’t be split into the left or the right, nor can it be merged with itself
Consider the left call complete!

Notes:

Same thing applies with the right, element 25 can’t be split to the left or the right, nor can it merge with itself.
Now we will merge them back in order: [5, 25]

Important concepts:

When making new recursive call, we are NOT making a new list, array, or a new set of elements.
Basically updating all the way back to the original list

Notes:

When merging back together, it will merge back from least to greatest.

Popcorn Hack: What will the final list be?

-2, 0, 2, 14 (on the right side) Answer: -9, -2, 0, 2, 5, 8, 14, 25

The mergeSort Method

//sudocode
mergeSort(myArray, low, high) {
    if (low < high) {
        middle = (low + high)/2; //find middle
        mergeSort(myArray, low, middle); //make a recursive call from low to middle (look at left hand side)
        mergeSort(myArray, middle + 1, high); //once low is no longer less than high, make a new recursive call (look at right hand side)
        merge (myArray, low, middle, high); //merge back together
    }
}

int [] myArray = {3, 4, 6, 8, 1, 2, 5, 7};

Steps:

Split the Array in half
Left side: {3, 4, 6, 8}; Right side {1, 2, 5, 7};

Compare the first indexes in each individual array (which would be index 0 and index 4)

Since 1<3, our new index 0 value would be 1 when we merge the array back together

Since 5>3, our new index 2 value would be 3 when we merge the array back together

Popcorn Hack: What will the final array return?

Answer: {}

Wait, but there’s an issue…

After comparing index 3 and index 7, we then need to compare index 3 and index, but there is no index 8…
Will recieve an index out of bounds exception.

No worries! Since we are done with the sort, we can just move the rest of the elements to the end of the array because we are already done sorting.

Index 3 will now become index 7.

Hacks

Create a 2D array either with just a regular array variable that you can recursively traverse through.
Each value in this 2D array must be a string that you can individually traverse through.
You must output a result of all string values that have a user inputted letter.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // Create a 2D array of strings
        String[][] grid = {
            {"apple", "banana", "cherry"},
            {"dog", "elephant", "fish"},
            {"grape", "horse", "iguana"}
        };

        // Get the user's input letter
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter a letter: ");
        char targetLetter = scanner.next().charAt(0);

        // Recursively traverse the 2D array and find strings with the target letter
        System.out.println("Strings containing the letter '" + targetLetter + "':");
        searchAndPrint(grid, targetLetter, 0, 0);
    }

    public static void searchAndPrint(String[][] grid, char targetLetter, int row, int col) {
        if (row >= grid.length) {
            return; // Base case: stop when we've reached the end of the rows
        }

        if (col >= grid[row].length) {
            searchAndPrint(grid, targetLetter, row + 1, 0); // Move to the next row
            return;
        }

        searchAndPrintInString(grid[row][col], targetLetter);

        searchAndPrint(grid, targetLetter, row, col + 1); // Move to the next column
    }

    public static void searchAndPrintInString(String str, char targetLetter) {
        if (str.contains(String.valueOf(targetLetter))) {
            System.out.println(str);
        }
    }
}


Main.main(null);

Enter a letter: Strings containing the letter 'a':
apple
banana
elephant
grape
iguana

Create your own merge chart (like the first image in this 10.2 lesson) with your own values from a list, array, or arraylist (doesn’t matter). Explain how recursion works in the merge chat.

// code in here
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};

        System.out.println("Original Array:");
        printArray(arr);

        mergeSort(arr);

        System.out.println("\nSorted Array:");
        printArray(arr);
    }

    public static void mergeSort(int[] arr) {
        int n = arr.length;
        if (n < 2) {
            return; // Array is already sorted if it contains 0 or 1 element
        }

        int mid = n / 2;
        int[] left = new int[mid];
        int[] right = new int[n - mid];

        // Copy data to left and right subarrays
        for (int i = 0; i < mid; i++) {
            left[i] = arr[i];
        }
        for (int i = mid; i < n; i++) {
            right[i - mid] = arr[i];
        }

        // Recursively sort the left and right subarrays
        mergeSort(left);
        mergeSort(right);

        // Merge the sorted left and right subarrays
        merge(arr, left, right);
    }

    public static void merge(int[] arr, int[] left, int[] right) {
        int n1 = left.length;
        int n2 = right.length;
        int i = 0, j = 0, k = 0;

        while (i < n1 && j < n2) {
            if (left[i] <= right[j]) {
                arr[k] = left[i];
                i++;
            } else {
                arr[k] = right[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = left[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = right[j];
            j++;
            k++;
        }
    }

    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}


MergeSort.main(null);

Original Array:
12 11 13 5 6 7 

Sorted Array:
5 6 7 11 12 13 

Recursion in Merge Sort

Merge Sort is a divide-and-conquer sorting algorithm that efficiently sorts an array by recursively breaking it into smaller subarrays, sorting those subarrays, and then merging them to produce a sorted array. Recursion plays a vital role in making Merge Sort possible and efficient. Here’s how recursion works in the Merge Sort algorithm:

Divide: The input array is divided into two equal (or nearly equal) halves. This process continues until each subarray contains only one or zero elements.
Conquer (Recursion): After dividing the array, the Merge Sort algorithm is recursively applied to each of the smaller subarrays. This recursive division and sorting continue until the base case is reached, which is when a subarray contains only one element (trivially sorted) or no elements.
Merge: Once the subarrays are sorted individually, they are merged together in a manner that ensures the combined array is sorted. The merging process also uses recursion to merge the smaller sorted subarrays into a larger sorted array.

The key idea is that when you break a problem into smaller subproblems, solve the subproblems, and then combine the solutions, you can efficiently solve the original problem. In Merge Sort:

The “divide” step splits the array into two halves, each of size approximately n/2 (n is the size of the original array).
The “conquer” step involves recursively sorting each of these smaller subarrays.
The “merge” step combines two sorted subarrays into a single sorted array, which is an efficient operation because you’re merging two already sorted sequences.

Recursion ensures that each subarray is sorted correctly, and then the merging step efficiently combines the sorted subarrays to produce a fully sorted array. This process continues until the entire array is sorted.

Recursion makes Merge Sort a stable and efficient sorting algorithm, with a time complexity of O(n log n) in the worst, average, and best cases, making it suitable for sorting large datasets.

U10 Recursion P1 Student • 55 min read

Description

10.1 Recursion

Vocabulary

Method Calling Itself

Calling With Different Parameters

Capturing Progression Through Recursion

Converting Recursion to Iteration

Recursive Version

Iterative Version

Traversing With Recursion

String Traversal

Array Traversal

ArrayList Object Traversal

Conclusion

10.2 Binary Search

Binary Search vs Linear Search

Popcorn hack:

Example of Binary Search with Recursion

Call 1

Call 2

Call 3

Recursive Logic behind Merge Sort

Notes:

Notes:

Notes:

Important concepts:

Notes:

Popcorn Hack: What will the final list be?

The mergeSort Method

Steps:

Popcorn Hack: What will the final array return?

Wait, but there’s an issue…

Hacks

Recursion in Merge Sort