10.1 Recursion

recursive calls are calling part of the method

  • there's a call stack to keep track of all the times that a recursive function has been called, as well as their parameters
  • calls from top to bottom, returns from bottom back to the top

Recursion vs loop:

  • iteration is repeating instructions repeatedly until condition is false
  • recursion used when big problem can be expressed in a smaller problem
  • difference: recursion uses function calls, iteration uses loops

See Fibonacci Hacks: here

class FiboRecursion extends Fibo {
        
    // default constructor
    public FiboRecursion() {
        super();
    }

    // takes input of number, calls constructor
    public FiboRecursion(int n) {
        super(n);
        
    }

    // the recursive function: type int so it feeds into self and returns a value
    public int fibNum(int n)
    {
        // if its the first 2 terms (0 or 1), set the data in the array and hashmap as 0 or 1 and return
        if (n <= 1) {
            this.setDataRec(n, n); // setData as 0 or 1
            return n;
        }
        int currentFibNum = fibNum(n-1) + fibNum(n-2); // sets the current fibonacci number to the sum of the previous two (recursion starts)
        this.setDataRec(n, currentFibNum); // sets data of the currentFibNum to the index of the fibNum (n)

        return currentFibNum; // returns for recursion
    }

    @Override // overwrite init function for the RECURSION
    protected void init() {
        // set name
        super.name = "recursion";

        // populate array
        for (int i = 0; i < super.size; i++) {
            super.list.add((long) 0);
            super.hash.put(i, super.list.clone());
        }

        // find the fib num up to super.size minus 1 because does not include
        fibNum(super.size - 1);

    }

    // better setdata: can put into specific index
    public void setDataRec(int n, long num) {
        super.list.set(n, num); // sets something into the array at certain index
        ArrayList<Long> smallList = new ArrayList<Long>(super.list.subList(0,n+1)); // cuts off the list at the fibonacci number length, as it already populates with the amount needed
        super.hash.put(n, smallList.clone()); // adds the list to hashmap
    }
}

10.2 Binary Search

  • data needs to be in order
  • keep halving array
  • O(log(2n)) vs linear search O(n)
  • can be used in things like dictionary searching

Linear Recursion:

  • function only makes a single call to itself (not multiple)

Selection sort:

  • find min element repeatedly, and putting that at the end of sorted part
  • results in descending order

Merge SOrt:

  • splits the problem or arraylist to sort, then merges together (divide and conquer)
  • divide input into two halves, calls itself for the halves, then merge (merge function)