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
 */
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);
    }

    /**
     * Recursively compute fibonacci numbers
     * The private version that actually does recursion
     * @param fibNumA a fib number
     * @param fibNumB the next fib number in the series for fibNumA
     * @param counter the number of additional steps to take in the series
     * @return the counterth fib number
     */
    private BigInteger fibonacciUtil(BigInteger fibNumA, BigInteger fibNumB, int counter)
    {
        System.out.println(counter + " " + fibNumA + " " + fibNumB);
        if (counter==1)
            return fibNumA.add(fibNumB);
        return fibonacciUtil(fibNumB, fibNumA.add(fibNumB), counter-1);
    }

    /**
     * Compute the nth fibonacci number
     * @param n the index of the desired number
     * @return the nth fibonacci number
     */
    public BigInteger fibonacci(int n) {
        if (n<=0) // make sure that the number being asked for is reasonable
            return BigInteger.valueOf(0);
        if (n<3)
            return BigInteger.valueOf(1);
        return fibonacciUtil(BigInteger.valueOf(1), BigInteger.valueOf(1), n-2);
    }

    /**
     * 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 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 int base2logB(int num) {
        if (num <= 0)
            return -1;
        if (num == 1)
            return 0;
        return base2logBUtil(num, 1);
    }

    private int base2logBUtil(int num, int upward) {
        if (upward > num)
            return -1; // stops 1 too late, so return -1
        return 1+base2logBUtil(num, upward * 2);
    }

    /**
     * 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);
        }
    }

    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;
    }

    int acount = 0;

    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;
    }

    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));
    }

    public int numOccur4(char ch, String str) {
        return numOccur4Util(ch, str, 0);
    }

    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);
    }
    
    public int numOccur5(char ch, String str) {
        if (str == null || str.length()==0)
            return 0;
        return numOccur5Util(ch, str, 0, 0);
    }

    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);
    }

    public int numOccur6(char ch, String str) {
        if (str == null || str.length()==0)
            return 0;
        return numOccur6Util(ch, str, 0);
    }
    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);
    }

    public static void main(String[] args)
    {
        Recurser r = new Recurser();
        System.out.println(r.base2log(50));
        System.out.println(r.base2log(65));
        System.out.println(r.base2logB(50));
        System.out.println(r.base2logB(65));
        //System.out.println(r.numOccur6('a', "a test a train"));
        //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--) {
        }
    }
}