Recursion

  • Recursive method
    • Method that calls itself
  • Contains at least one base case that halts recursion
  • Each recursive call has own local vars
  • Parameters value take progress of recursive process ## Example
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

Double Recursion Example 

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

9

Binary Search

  • Splitting sorted list into 2 bounds ## Example 
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

  • Sorts array lists
  • Divide and conquers
  • Copies original elements in a temporary array and then merge sorts both sides of the array list and then merges both sides together

Recursion Tree

  • Way to visualize the call of a recursive sequence
    • Look at calls
    • Work from top to bottom