/*
 * RecursiveMethods.java
 * 
 * Additional practice with recursive methods
 */

public class RecursiveMethods {
    /*
     * factorial - uses recursion to find the factorial of an integer n.
     * 
     * Note: to handle larger results, we could use long instead of int.
     */
    public static int factorial(int n) {
        if (n <= 1) {
            return 1;
        } else {
            return n * factorial(n-1);
        }
    }

    /*
     * alternative version with a single return statement and 
     * a base case that is implied by the initial value 
     * assigned to the return variable.
     */
    public static int factorial2(int n) {
        int fact = 1;

        if (n >= 2) {
            fact = n * factorial2(n-1);
        }

        return fact;
    }

    /*
     * countN - recursively determines the number of times that the 
     * integer n appears in the portion of the array arr that goes 
     * from the specified index to the end of the array. 
     * 
     * We assume that arr is not null and that index is non-negative.
     * 
     * To determine how many times n appears in the entire array, 
     * use an initial call in which index is 0.
     */
    public static int countN(int n, int[] arr, int index) {

	int count;
        // base case is when index >= arr.length, 
        // since that means we're at or beyond the end of the array.
        // This will also handle the case in which the 
        // entire array has a length of 0.
        if ( arr == null || (index < 0 || index >= arr.length) ) {
            count = 0;
        } else {
            // note that we increase the index when we make the
            // recursive call to reduce the portion of the array
            // that we are focused on
            int countRest = countN(n, arr, index + 1);
            
            if (arr[index] == n) {
                count = countRest + 1;
            } else {
                count = countRest;
            }
        }
	return( count );
    }

    /*
     * alternative version with a single return statement and 
     * a base case that is implied by the initial value 
     * assigned to the return variable.
     */
    public static int countN2(int n, int[] arr, int index) {
        int count = 0;

        if ( arr != null && (index >= 0 && index < arr.length-1) ) {
    	    if (arr[index] == n) {
                count = countN2(n, arr, index+1) + 1;
            } else {
                count = countN2(n, arr, index+1);
            }
        }
        
        return count;
    }

    /*
     * findMin - recursively determines the smallest value in 
     * the portion of the array arr that goes from the specified index 
     * to the end of the array.
     * 
     * We assume arr has at least one element and index is non-negative.
     * 
     * To determine the smallest value in the entire array, 
     * use an initial call in which 0 is the index.
     */
    public static int findMin(int[] arr, int index) {
	if (arr == null || index < 0 || index >= arr.length)
	    throw new IllegalArgumentException();
	
	int min;

        // base case: we are focused on a portion
        // of the array that has only one element, 
        // so that element must be the min.
        if (index == arr.length - 1) {
            min = arr[index];
        } else {
            int minInRest = findMin(arr, index + 1);
            if (arr[index] < minInRest) {
                min = arr[index];
            } else {
                min = minInRest;
            }
        }

	return(min);
    }

    /*
     * alternative version with a single return statement 
     */
    public static int findMin2(int[] arr, int index) {
	if (arr == null || index < 0 || index >= arr.length)
	    throw new IllegalArgumentException();

        int min;

        if (index == arr.length - 1) {
            min = arr[arr.length - 1];
        } else {
            // the recursive case returns the minimum of
            // the element at the current index and the
            // element returned from the recursive call.
            min = Math.min(arr[index], findMin2(arr, index + 1));
        }
        
        return min;
    }

    /*
     * Note: it is also possible to have the index parameter represent 
     * the *end* of the portion of the array that we are focused on.
     * 
     * In this approach, you would pass in arr.length-1 as the initial index,
     * you would *subtract* one when making the recursive call, and 
     * the base case would be when index == 0.
     * 
     * Here is an implementation that takes that approach.
     */
    public static int findMin3(int[] arr, int index) {
        int min;

	if (arr == null || index < 0 || index >= arr.length)
	    throw new IllegalArgumentException();

        if (index == 0) {
            min = arr[0];
        } else {
            min = Math.min(arr[index], findMin3(arr, index - 1));
        }
        
        return min;
    }

    public static void main(String args[]) {
        System.out.println(factorial(10));
        System.out.println(factorial2(10));

        int[] a = { 13, 2, 2, 7, 2, 3, 2, 4, 11, 5, 7, 3 };
        System.out.println(countN(2, a, 0));
        System.out.println(countN2(2, a, 0));

        System.out.println(findMin(a, 0));
        System.out.println(findMin2(a, 0));
        System.out.println(findMin3(a, a.length-1));
    }
}