12.6 Recussion

    static int divide(int a, int b) {
        if (a - b < b) {
            return 1;
        } else {
            return divide(a - b, b) + 1;
        }
    }
    static int multiple(int a, int b) {
        if (b == 0) {
            return 0;
        } else {
            return multiple(a, b - 1) + a;
        }
    }
    //5! (5*4*3*2*1)=120
    static int factorial(int n) {
        if (n == 1) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
    //O(2^n) Fn= Fn-1+ Fn-2
    //F1=1,F2=1,F3=2,F4=3,F5=5,F6=8,F7=13
    static int fibonacci1(int n) {
        if (n == 0) {return 0;}
        if (n == 1) {return 1;} 
        else {
            return fibonacci1(n - 1) 
                    + fibonacci1(n - 2);
        }
    }

    //optimize cracking code O(n)
    static int[] fib = new int[100];//max=100;
    static int fibonacci2(int i) {
        if (i == 0) {return 0;}
        if (i == 1) {return 1;} 
        if (fib[i] != 0){return fib[i];}
        fib[i] = fibonacci2(i - 1) + fibonacci2(i - 2);
        return fib[i];
    }
    //descending(4)=4 3 2 1
    static void descending(int a) {
        if (a == 1) {
            System.out.print(a);
        } else {
            System.out.print(a + " ");
            descending(a - 1);
        }
    }
    //exponentiation(4, 3)=4^3=64
    static int exponentiation(int a, int b) {
        if (b == 0) {
            return 1;
        } else {
            return a * exponentiation(a, b - 1);
        }

    }
    //decToBinary(10) =1010
    //decToBinary(156)=10011100
    static String decToBinary(int x) {
        if (x == 1) {
            return "1";
        } else {
            return decToBinary(x / 2) + (x % 2);
        }
    }
/*
    //int[] list4 = new int[] { 1, 2, 3, 4, 5, 6, 7, 8 };
    //findMin(list4, 0, list4.length - 1, 1)
    static int findMin(int[] x, int first, int last, int restPoint) {

        print(x, first, last);
        int mid = (first + last) / 2;
        if (x[mid] == restPoint) {
            return x[mid];
        } else if (x[mid] > x[last]) {
            return findMin(x, mid, last, restPoint);
        } else {
            return findMin(x, first, mid, restPoint);
        }
    }

    static void print(int[] x, int first, int last) {
        for (; first < last; first++) {
            System.out.print(x[first] + " ");
        }
        System.out.println();
    }
    */
    //int[] list7 = new int[] { 5, 6, 7, 8,  2, 3, 4 };
    //findMinFromArray(list7, 0 , list7[0])
    private static int findMinFromArray(int[] iArray, int index, int min) {
        if(index <= (iArray.length - 1)){
            if(iArray[index] < min){
                min = iArray[index];
            }
            System.out.println("Before: " + "Index = " + index + " | Min = " + min);
            return findMinFromArray(iArray, index + 1, min);
        }
        System.out.println("After: " + "Index = " + index + " | Min = " + min);
        return min;
    }

public static void main(String[] args) {

        HashSet<Integer> temp = new HashSet<Integer>();

        // TODO Auto-generated method stub
        System.out.println("Division recussion (10/2)= " + divide(10, 2));
        System.out.println("Multiple recussion (10*4)= " + multiple(10, 4));
        System.out.println("Factorial of 5! (5*4*3*2*1)=" + factorial(5));
        System.out.println("O(2^n)Fibonacci1 of 5 Fn= Fn-1+ Fn-2 =" + fibonacci1(7));//O(2^n)
        System.out.println("O(n)  fibonacci2 of 5 Fn= Fn-1+ Fn-2 =" + fibonacci2(7));//optimize cracking code ,O(n)


        System.out.println("descending");
        descending(4);

        System.out.println("\nexponentiation 4^3=" + exponentiation(4, 3));

        System.out.println("decToBinary(10) =" + decToBinary(10));
        System.out.println("decToBinary(156)=" + decToBinary(156));

        // find min of this
        // 1 2 3 4 5 6 7 8
        // 3 4 5 6 7 8 1 2
        // 8 1 2 3 4 5 6 7
        // 5 6 7 8 1 2 3 4

        int[] list4 = new int[] { 1, 2, 3, 4, 5, 6, 7, 8 };
        int[] list5 = new int[] { 3, 4, 5, 6, 7, 8, 1, 2 };
        int[] list6 = new int[] { 8, 1, 2, 3, 4, 5, 6, 7 };
        int[] list7 = new int[] { 5, 6, 7, 8,  2, 3, 4 };
        //System.out.println("=============findMin Recussion =============");
        //System.out.println("findMin 1="    + findMin(list4, 0, list4.length - 1, 1) + "\n");
        //System.out.println("=============findMin Recussion =============");
        //System.out.println("findMin 2="+ findMin(list5, 0, list5.length - 1, 1) + "\n");
        //System.out.println("=============findMin Recussion =============");
        //System.out.println("findMin 3="    + findMin(list6, 0, list6.length - 1, 1) + "\n");
        //System.out.println("=============findMin Recussion =============");
        //System.out.println("findMin 4="    + findMin(list7, 0, list7.length - 1, list7[0]) + "\n");
        System.out.println("=============findMin Recussion =============");
        System.out.println("findMin ="    + findMinFromArray(list7, 0 , list7[0]) + "\n");

    }