Recursion

A recursive method is a method that calls itself repeatedly
made of a base case and a recursive call
after x calls, the base case is reached, the loop is stopped, and a value is returned
Recursive calls are calls part of a method
Each call has unique values until base case is reached
Recursive methods have a call stack that keeps track of all the times the function is called

//Iterative Code
public static int multiply(int a, int b) {
    int sum = 0;
    for (int i =0; i < b; i++) {
        sum += a;
    }
    return sum;
}

Recursions are similar to loops and can be written as such
Iteration vs. Recursion:
Iteration is used to execute instructions repeadetly unitl a certain condition
Recursion is used when the solution to a bigger problem can be expressed as smaller problems
function calls vs. for and while loops

public static int multiply(int a, int b){
    if (b == 0) {
        return 0;
    } else {
        return multiply(a, b-1) + a;
    }
}

Binary Search

search algorithm
data must be in order
splits array in half until the value is found
more efficient than linear search

Linear Recursion + Selection Sort

Linear Recursion: a function that only makes a single call to itself each time the function runs
Selection Sort: the algorithm works by repeatedly finding the minimum element from the unsorted part and putting it at the end of the sorted part

int factorial (int n)
{
    if (n == 0) return 1;
    return n * factorial (n-1);
}

Merge Sort

can be used to sort ArrayList structures
Uses a deivide and conquer alogirthm
divides the input array into halves, calls itself and then merges the two sorted halves
merge() function is used to merge the two halves together