
/**
 * 
 * All these problems should be solved recursively - not with the use of rarely 
 * used library functions or for or while loops.
 * 
 * You can use recursive helper functions if you want, but most of the problems given
 * here do not require them.
 * 
 * YOU ONLY NEED TO SOLVE 3 OF THE 4 RECURSION PROBLEMS HERE
 * 
 * Leave the problem you've decided not to solve blank, and leave a comment
 * saying you've decided to skip it.
 * 
 * @author hewner
 *
 */
public class Recursion {

	/**
	 * An imaginary game consists of a series of rounds.
	 * A players score in the game is the last round they win.
	 * So for example, if a player's record was WLWLLL, their 
	 * score would be 3 because their last win was in the 3rd round. 
	 * 
	 * Write a function that computes the score, given a series of wins
	 * and losses.
	 * 
	 * For example:
	 * 
	 * "LLL" returns 0
	 * "WLL" returns 1
	 * "LLLLLLW" returns 7
	 * "LLLLLLWL" returns 7
	 * "" returns 0
	 * 
	 * Use recursion to solve this problem, not creative use of string functions 
	 * like indexOf.  Also do not use for/while loops.
	 * 
	 */
	public static int findLastWin(String input) {
		if(input.isEmpty()) return 0;
		if(input.charAt(input.length() - 1) == 'W')
			return input.length();
		return findLastWin(input.substring(0,input.length() - 1));
	}
	
	/**
	 * We'll call a string a "hidden word" in another string if all its letters
	 * occur in the same order in the other string, but maybe not consecutively.
	 * 
	 * so "cat" is a hidden word in "chatter"
	 * 
	 * Write a function given a string to search and a possible hidden word, returns
	 * true if the hidden word occur in the string.  For example:
	 * 
	 * hasHiddenWord("reading", "eig") returns true
	 * hasHiddenWord("reading", "gie") returns false
	 * hasHiddenWord("abcde","aae") returns false
	 * hasHiddenWord("hat","hat") returns true
	 * hasHiddenWord("at","hat") returns false
	 * hasHiddenWord("anything","") returns true
	 * hasHiddenWord("","") returns true
	 * 
	 * Use recursion to solve this problem, not for/while loops.
	 * 
	 * @param stringToSearch
	 * @param hiddenWord
	 */
	public static boolean hasHiddenWord(String stringToSearch, String hiddenWord) {
		if(hiddenWord.isEmpty()) return true;
		if(hiddenWord.length() > stringToSearch.length()) return false;
		if(stringToSearch.charAt(0) == hiddenWord.charAt(0)) {
			return hasHiddenWord(stringToSearch.substring(1), hiddenWord.substring(1));
		} else {
			return hasHiddenWord(stringToSearch.substring(1), hiddenWord);
		}
	}
	
	/**
	 * Returns true if the first number is an positive whole number power of the second.
	 * 
	 * Use recursion to solve this problem, not for/while loops or the log functions in Math.
	 * 
	 * 
	 * For example:
	 * 
	 * isPowerOf(8,2) returns true
	 * isPowerOf(8,3) returns false
	 * isPowerOf(27,3) returns true
	 * isPowerOf(3,27) returns false
	 * isPowerOf(24,2) returns false
	 * isPowerOf(9,9) returns true
	 * isPowerOf(1,2) returns false (has to be a POSITIVE whole number power)
	 * 
	 */
	public static boolean isPowerOf(int larger, int smaller) {
		if(larger == smaller) return true;
		if(larger % smaller != 0) return false;
		return isPowerOf(larger/smaller,smaller);
	}
	
	/**
	 * Returns true of the array is alternating positive and negative numbers, 
	 * starting with positive.  Zero is neither positive or negative.
	 * 
	 * You can assume the array has an even length, though it may be empty
	 * 
	 * Use recursion to solve this problem, not for/while loops.
	 * 
	 * 
	 * For example:
	 * 
	 * alternatingArray([1,-3,7,-6]) returns true
	 * alternatingArray([1,-3,7,8]) returns false
	 * alternatingArray([-5,1,-3,7]) returns false (MUST start positive)
	 * alternatingArray([1,-3,7,0]) returns false (zero neither positive or negative)
	 * alternatingArray([]) returns true
	 * 
	 * HINT: you may want a recursive helper function for this one
	 */
	public static boolean alternatingArray(int[] input) {
		return alternatingArray(input,0);
	}
	
	private static boolean alternatingArray(int[] input, int index) {
		if(index >= input.length) return true;
		if(input[index] < 1) return false;
		if(input[index + 1] > -1) return false;
		return alternatingArray(input, index + 2);
	}
	
	
}
