// Arup Guha
// 3/10/2016
// Recursion Examples for Junior Knights

public class recursion {

    final public static double TIP_RATE = 0.15;

    // Returns base raised to the power exponent, exponent must be non-negative.
    public static int power(int base, int exponent) {
        if ( exponent == 0 )
            return 1;
        else
            return (base*power(base, exponent-1));
    }

    // Returns 1 + 2 + ... + n, n must be non-negative.
    public static int triangleNumber(int n) {
        if ( n == 0 )
            return 0;
        else
            return (n + triangleNumber(n-1));
    }

    // Returns 1 + 2 + ... + n, n must be non-negative.
    public static int triangleNumberIter(int n) {
        int index, sum = 0;
        for (index=1; index <=n; index++)
            sum = sum + index;
        return sum;
    }

    // Returns n!, 0 <= n <= 12 is required.
    public static int fact(int n) {
        if (n == 0)
            return 1;
        else
            return n * fact(n-1);
    }

    // Returns the nth Fibonacci number. 0 < n < 46 (or so)
    public static int fib(int n) {
        if (n < 3)
            return 1;
        else
            return fib(n-1) + fib(n-2);
    }

    // Prints out a tip chart from dollar amount start to end.
    public static void tipChart (int start, int end) {

        if (start <= end)  {
            System.out.print("On a meal of $"+start);
            System.out.println(", tip $"+ start*TIP_RATE+".");
            tipChart(start + 1, end);
        }
    }

    // Returns x * y.
    public static int mult(int x, int y) {

        if ( y < 0 )
            return -mult(x,-y);
        else if ( x < 0 )
            return -mult(-x, y);
        else if ((x == 0 ) || (y == 0 ))
            return 0;
        else
            return (x + mult(x, y-1));
    }

    // Returns true iff searchval is in values[low..high]. It's required that values is sorted.
    public static boolean binSearch(int[] values, int low, int high, int searchval) {

        if (low <= high) {

            int mid = (low+high)/2;
            if (searchval < values[mid])
                return binSearch(values, low, mid-1, searchval);
            else if (searchval > values[mid])
                return binSearch(values, mid+1, high, searchval);
            else
                return true;
        }

        return false;
    }

    // Returns the sum of the digits of n. n must be non-negative.
    public static int digitSum(int n) {
        if (n > 0)
            return n%10 + digitSum(n/10);
        return 0;
    }

    // Prints out a set of moves to solve the Towers of Hanoi with n disks starting from tower
    // start and ending at tower end. start != end must be true and both start and end must be
    // taken from the set {1,2,3}.
    public static void towers(int n, int start, int end) {
        if (n > 0) {
            int mid = 6 - start - end;
            towers(n-1, start, mid);
            System.out.print("Move disk "+n+" from tower ");
            System.out.println(start+" to tower "+end+".");
            towers(n-1,mid,end);
        }
    }

    public static void main(String[] args) {

        // Lots of tests.
        System.out.println("3 to the 5 is "+power(3, 5));
        System.out.println("The 100th triangle number is "+triangleNumber(100));
        System.out.println("The 100th triangle number is "+triangleNumberIter(100));
        System.out.println("12! = "+fact(12));
        System.out.println("Fib(10) = "+fib(10)+"  and fib(46) = "+fib(46));
        tipChart(10, 30);
        System.out.println("8 x 5 is "+mult(8, 5));
        System.out.println("-9 x -6 is "+mult(-9,-6));
        System.out.println("7 x -12 is "+mult(7,-12));
        System.out.println("-13 x 9 is "+mult(-13,9));
        System.out.println("sum of the digits of 16765187 is "+digitSum(16765187));
        towers(5, 1, 3);

        // Binary Search Test
        int[] array = {2, 5, 9, 10, 11, 22, 45, 98, 100, 192};
        for (int i=0; i<200; i++)
            if (binSearch(array, 0, array.length-1, i) == true)
                System.out.println("Found "+i);
    }

}