import java.math.BigInteger;
import java.util.ArrayList;

/**
 * Simple recursion functions 
 * 
 * @author gtowell 
 * Created: Oct 2019
 * Modified: Feb 2020
 * Modified: Oct 27, 2020
 * Modified: Oct 20, 2020
 * * Modified: August 11, 2020
 */
public class Recurser {
    /**
     * A bad recursive function. It lacks a base case so the recursion does not stop.
     * @param c the number to count down from
     */
    public void badRecurse(int c) {  
    	System.out.println("A" + c);
	    badRecurse(c-1);
    }
    
    /**
     * A good recursive function to count down from a number
     * @param c the number to count down from
     */
    public void goodRecurse(int c)
    {
    	System.out.println("B" + c);
	    if (c<=0) return;
	    goodRecurse(c-1);
    }


    /**
     * A recursive function to add two positive numbers
     * @param num1 one of the numbers
     * @param num2 another number
     * @return the sum of the two numbers
     */
    public int rAdder(int num1, int num2) {
        if (num2<=0) 
            return num1;
        return rAdder(num1+1, num2-1);
    }
    /**
     * Alternate recursive function to add two positive numbers
     * @param num1 one of the numbers
     * @param num2 another number
     * @return the sum of the two numbers
     */
    public int rAdderB(int num1, int num2) {
        if (num2<=0) 
            return 0;
        return 1+rAdderB(num1, num2-1);
    }

    /**
     * Build up an ArrayList containing the numbers 1..count
     * This code does not handle negative numbers, at all.
     * @param count the max number in the returned ArrayList
     * @return an ArrayList containing the numbers 1..count
     */
    public ArrayList<Integer> rAccmulate(int count)
    {
        if (count <= 0)
            return new ArrayList<Integer>();
        ArrayList<Integer> alAcc = rAccmulate(count-1);
        alAcc.add(count);
        return alAcc;
    } 

    /**
     * Implement multiplication recursively using addition
     * For example, given the args 7 and 4 write a recusive function 
     * that computes 7+7+7+7
     * @param i1 a number
     * @param i2 another number
     * @return i1*i2
     */
    public int multiply(int i1, int i2) {
        if (i2<=0) return 0;
        return i1+multiply(i1,i2-1);
    }

    /**
     * Write a recusrsive function to add all the values in the array
     * Hint, this method should not be recursive.  Rather make a 
     * private recursive function and call that from here
     * @param array
     * @return the sum of the numbers in the array
     */
    public int addArray(int[] array) {
        return addArray(array, 0);
    }

    /**
     * Private recursive function to actually do the work for 
     * the public addArray
     * @param array the function whose elements are to be added
     * @param loc the current location in the function
     * @return the sum of all elements in the array from loc to the end
     */
    private int addArray(int[] array, int loc) {
        if (loc>=array.length)
            return 0;
        return array[loc] + addArray(array, loc+1);
    }

    /**
     * Compute the base N log of a number.  The integer part only.  So baseNlog(2,7)==2
     * @param n the log base
     * @param num the number to compute for
     * @return the base N log, integer part.
     */
    public int baseNlog(int n, int num) {
        if (n<=1) return 0;
        if (num<n) return 0;
        return 1+baseNlog(n, num/n);
    }

    /**
     * Return true iff the string is a palindrome.
     * @param s -- the string to be checked
     * @return true iff the provided string is a palindrome
     */
    public boolean palindrome(String s){
        return isPalindromeUtil(s, 0, s.length()-1);
    }
    /**
     * Internal helper function for palindrome.  This function works by checking the 0 char against
     * the length()-1 char, then the 1 char against the length-2, ...
     * So at each recursive call increment lower index and decrement the higher
     * @param s the string to check
     * @param idx the lower index of a letter to check
     * @param lidx the higher index of another letter to check
     * @return true if the string is a palindrome
     */
    private boolean isPalindromeUtil(String s, int idx, int lidx) {
        if (idx>=lidx) return true;
        return s.charAt(idx)==s.charAt(lidx) && isPalindromeUtil(s, idx+1, lidx-1);
    }

    /**
     * Alternate palindrome recursive formulation. This works by checking the first and last letters.  If they agree, then strip them off and recurse.
     * @param s the stirng to be checked
     * @return true iff the string is a palindrome.
     */
    public boolean palindromeb(String s) {
        if (s.length()<=1) return true;
        if (s.charAt(0) != s.charAt(s.length()-1)) return false;
        return palindromeb(s.substring(1, s.length()-1));
    }
    
    /**
     * Recursive implementation of a for loop (or while)
     * @param limit the bound
     */
    public void forLoop(int limit) {
        forLoopUtil(limit, 0);
    }
    /**
     * private utility func implementing for loop.
     * @param limit -- the bound
     * @param current -- the incremented variable
     */
    private void forLoopUtil(int limit, int current) {
        System.out.println(current);
        if (current<limit) {
            forLoopUtil(limit, current+1);
        }
    }

    /**
     * Count the number of occurrences of a letter ina string
     * This one is Wrong
     * @param ch the letter
     * @param str the string
     * @return the count (wrong)
     */
    public int numOccur1(char ch, String str) {
        if (str == null || str.equals("")) {
            return 0;
        }
        int count = 0;
        if (str.charAt(0) == ch) {
            count++;
        }
        numOccur1(ch, str.substring(1));
        return count;
    }

    // a private variable used by numOccur2
    private int acount = 0;

    /**
     * Count the number of occurrences of a letter ina string
     * Works, but poorly
     * @param ch the letter
     * @param str the string
     * @return the count
     */
    public int numOccur2(char ch, String str) {
        if (str == null || str.equals("")) {
            return 0;
        }
        if (str.charAt(0) == ch) {
            acount++;
        }
        numOccur2(ch, str.substring(1));
        return acount;
    }

    /**
     * Count the number of occurrences of a letter in a string
     * Finbaly one that works pretty well
     * @param ch the letter
     * @param str the string
     * @return the count
     */
    public int numOccur3(char ch, String str) {
        if (str == null || str.equals("")) { return 0; }
        int count = 0;
        if (str.charAt(0) == ch) { count = 1; }
        return count + numOccur3(ch, str.substring(1));
    }

    /**
     * Yes another count the number of occurences of a letter in a string
     * This one uses a private recursive function
     * @param ch the letter
     * @param str the string
     * @return the count
     */
    public int numOccur4(char ch, String str) {
        //The idea here is to pass the starting count -- 0 -- into the private func
        return numOccur4Util(ch, str, 0);
    }

    /**
     * the Private recursive part of counter 4
     * @param ch the letter
     * @param str the string
     * @param count the current count
     * @return the count
     */
    private int numOccur4Util(char ch, String str, int count) {
        if (str == null || str.equals("")) {
            return count;
        }
        if (str.charAt(0) == ch) {
            count++;
        }
        return numOccur4Util(ch, str.substring(1), count);
    }
    
    /**
     * Better version of number 4.  Checks preconditions first.
     * Also, indexes through string rather than substringing. 
     * @param ch the letter 
     * @param str the string 
     * @return the count
     */
    public int numOccur5(char ch, String str) {
        if (str == null || str.length()==0)
            return 0;
        return numOccur5Util(ch, str, 0, 0);
    }

    /**
     * The private version of number 5
     * @param ch the letter
     * @param str the string
     * @param loc the location to look and continue to the right from
     * @param count the current count
     * @return the count
     */
    private int numOccur5Util(char ch, String str, int loc, int count) {
        if (loc >= str.length())
            return count;
        if (str.charAt(loc) == ch) { count++; }
        return numOccur5Util(ch, str, loc+1, count);
    }

    /**
     * Last version of a the counter
     * @param ch the char
     * @param str the string
     * @return the count
     */
    public int numOccur6(char ch, String str) {
        if (str == null || str.length() == 0)
            return 0;
        return numOccur6Util(ch, str, 0);
    }
    /**
     * The private version of version 6.  This one acts much like version 3
     * @param ch the char
     * @param str the string
     * @param loc the location in the string
     * @return
     */
    private int numOccur6Util(char ch, String str, int loc) {
        if (loc >= str.length())
            return 0;
        int cc = 0;
        if (str.charAt(loc) == ch) { cc=1; }
        return cc+numOccur6Util(ch, str, loc+1);
    }

    /**
     * Print the given char the number of times given by num consecutively on 
     * the same line. After the last, print a newline.
     * @param ch the char to print
     * @param num the number of times to print the char
     */
    public void rowOfChars(char ch, int num) {
        if (num <= 0) {
            System.out.println();
            return;
        }
        System.out.print(ch);
        rowOfChars(ch, num - 1);
    }
        
    /**
    * Compute the base 2 log of a number.  
    * The integer part only.  So base2log(7)==2
    * @param num the number to compute for
    * @return the base 2 log, integer part.
    */
    public int base2log(int num) {
        if (num==1) return 0;
        return 1+base2log(num/2);
    }

    
    public static void main(String[] args)
    {
        Recurser r = new Recurser();
        System.out.println(r.numOccur6('a', "a test a train"));
        r.rowOfChars('d', 17);
        r.rowOfChars('X', 15);
        System.out.println(r.base2log(7));
        System.out.println(r.base2log(16));
        System.out.println(r.base2log(23));

        //r.badRecurse(5);
        //r.forLoop(8450);
        //System.out.println(r.palindromeb("madamm"));
        //r.goodRecurse(5);
        //int[] arr = {1,2,3,4,5,6,7,8,9};
        //System.out.println(r.addArray(arr));
        //System.out.println("Multiply 7,6 = " + r.multiply(6,7));
        //System.out.println("Result: " + r.fibonacci(472));
        //System.out.println(r.rAdder(5, 6));
        //System.out.println(r.rAccmulate(10));
    }

    public void loop(int c) {
        for (int i = c; i >= 0; i--) {
        }
    }
}