Intro to Recursion

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 example(int n) {
    if (n > 0)
        example (n-1);
}

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 int dblRecur(int n) {
    if (n > 0)
        return n + dblRecur(n/2) + dblRecur(n/3);
    return 0;
}
dblRecur(5);

9

prints out ; computer, mputer, uter, er, then the first letter of each

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

eumc

Binary Search with Equations

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

used to sort arrayLists
Uses a divide and conquer algorithm to sort ArrayList
- Divides the array into halves first, and then calls itself for the two different halves in order to sort them
- merges the two sorted halves into one list
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
think about: mergeSort (myList) { mergeSort(left); mergeSort(right); mergeSort (left & right) }

Recursion Tree

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

Vocab

Introduction to Recursion

a method that calls itself
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

Big O notation

for Hash map, Binary Search, Single loop, Nested Loop
describes the set of algorithms that run worse, better, or at a certain given speed
represents the number of operations performed

Merge Sort

can be used to sort arraylists
Uses a divide and conquer algorithm
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 list
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